xanthe-cat
commented
8 months ago This documentation is close to being ready, but I suspect more of the content will need to be refined as ongoing testing is still turning up a number of oddities.
As a result of this testing I can foresee a slew of issues to raise, and I am wondering whether you would like them to be raised as separate issues:
- in production mode the FFT selection code for Fermat numbers 16 and [18,22] chooses unworkable lengths because of the limited radices supporting Fermats, which may also affect Mersennes of similarly small size (I can see reasons pro and contra); — issue #3 raised; the workaround seems to be successful for these Fermats. ETA: the documentation describes the workaround needed.
in production mode this default FFT then cannot be over-ridden in these cases (why?);solved; mostly, except for F14 which uses a ridiculous FFT of 7K on AVX2 (this is also the case for F15 and F16 but 7K is apparently workable). On SSE2 Mlucas can use 4K for these tiny exponents. ETA: the problem of the 7K FFT length is due to thefermat.cfghaving a poor timing statistic for 4K relative to 7K. One gross workaround would be to simply change the data infermat.cfgso that it is monotonically increasing, as described in the Mlucas README. Another issue, e.g. of the tiny 4K radix producing theCY routines with radix < 16 do not support shifted residues!error, is similarly worked around by editing thefermat.cfgfile to use the preferred radix set (16 8 16).- again in production mode, the Pépin test for the cases of 17 and 23 doesn’t save the final residue at 2m–1 iterations to the fm and qm save files, so the most recent checkpoint is unusable for further testing; — issue #4 raised; none of the completed Pépin tests for [15,20] and 23 saved. ETA: this is now fixed.
- the various radix files have incorrect/misleading ‘7,8,9,15 and their multiples!’ errors about radices supporting Fermat modular squaring (the correct values are evidently 7,8,15,63);
- Suyama test appears as though it cannot be carried out correctly, as a result of 3. — this will probably be trivial if issue #4 is solved; though it may be a separate bug relating to restarting an interrupted PRP test, so I’m waiting to see the outcome of solving one problem before raising this as well. ETA: there was one other bug preventing the Suyama test from correctly being carried out (the PRP base issue #5) which is now resolved.
There’s also a variety of errors that crop up during the running of config-fermat.sh which may be actual code errors versus numeric incompatibility of some FFT sizes with the number being tested.
tdulcet
Introduction to Fermat number testing with Mlucas
Mlucas is a powerful Mersenne primality testing and factoring package which supports Lucas–Lehmer testing, Fermat probable primality testing, and Pollard p–1 factorisation; justly, most applications of the software have concentrated on examination of the Mersenne numbers, however Mlucas is also capable of testing the primality of Fermat numbers, testing the compositeness of Fermat cofactors, and running p–1 factorisation on Fermat numbers. This post and others hope to fill in several lacunae in the Mlucas documentation with respect to Fermat number testing.
Mlucas build notes
The Fermat modular squaring code is architecture-specific, ideally requiring Mlucas to be built with one of the SIMD modes (AVX, AVX2, SSE2, etc). This should be handled automatically by the
makemake.shscript for most hardware, including x86, however if Fermat modular squaring is not natively supported, there may be workarounds available.For example, Apple Silicon is ASIMD, meaning a native Mlucas build cannot test Fermat numbers. The answer is to build an SSE2 Mlucas on an Intel-based Mac, which should be capable of running under Rosetta emulation on Apple Silicon, at the penalty of a significant performance hit for larger exponents.
(When compiling on Intel with the intention of building a compatible version for Apple Silicon, the Makefile requires static linking of the GMP library, by the following alteration to the linker flags:
LDLIBS = -Bstatic ${LD_ARGS[@]} -BdynamicStatic linking of libraries is usually not recommended, and this may not be a solution in all possible cases.)Fermat self-testing and populating fermat.cfg
Assuming you have a working build, Mlucas allows any Fermat number Fm = 22m + 1 with exponent m in the range [14,63] to be entered as an argument for self-testing, by using the
-fflag like so:./Mlucas -f <exponent> -iters <number> [-fft <fft_length>]However, the software only provides fast Fourier transforms (FFTs) up to 512M in length, which further limits the largest Fermat number that may be tested, up to F33.
The
-itersflag is mandatory and should be followed by a number less than a million; the recommended values for-itersto be set to are 100, 1000, or 10000, since the self-testing code has correct residues for all Fermat numbers [14,33] saved, and any error in the test result will be immediately discovered.Mlucas does not support Fermat testing for all possible FFT lengths. Generally, FFTs for testing Mersenne numbers are available for any length k·2n K, where k = [8,15], n ≥ 0. In the case of Fermat numbers however, only the subset k = {8, 14, 15} supports Fermat testing, along with k = 63 when n ≥ 4.
When self-testing Mlucas for Mersenne numbers, a command such as
./Mlucas -s allconfigures Mlucas for the majority of FFT lengths and saves the results inmlucas.cfg. A similar process must be carried out for the Fermat numbers, using the./Mlucas -fcommand above, which saves results in the filefermat.cfg.A script
config-fermat.shhas been written to automate the generation of thefermat.cfgfile using the set of possible FFT lengths. After the license, the next few lines declare some variables which may be customised as desired (for example, 10000 iterations will require significant runtime at the largest possible FFT sizes):The script should be invoked from the build directory, typically
obj, with the following command, which may include as parameters any cpu-specific options, such as-coreor-cpu:Once self-testing has occurred, production work on Fermat numbers may be carried out using a
worktodofile (Mlucas 20.x:worktodo.ini; Mlucas 21:worktodo.txt) with entries in one of the several formats below.Only assignments for ECM factoring of Fermat numbers are distributed by Primenet, so work assignments cannot be obtained for Fermat numbers using the
primenet.pyscript. However p–1 results may be submitted to mersenne.org as Manual results.Primality testing: Pépin’s test
For the Pépin test, the
worktodoformat is simply:Fermat numbers in the range [14,22] may select a non-optimal FFT length by default in production mode. If this is the case, the FFT may be overridden using the command:
The optimal FFT lengths vary from 4K up to 512M as shown in the table below.
Currently, all Fermat numbers up to F30 have received a Pépin test, and moreover F31 and F32 are known to be composite. However, the character of their cofactors is unknown; and as for F33, this is yet to be tested for primality.
The Pépin test uses Gerbicz error checking (GEC) to assure the reliability of the computation, however residue shifting is not implemented for Fermat modular squaring with GEC. Thus when invoking Mlucas the flag
-shift 0must be added to the Mlucas command line:If non-zero residue shifting is used, the Pépin test will not be able to progress beyond the millionth iteration (the default interval for GEC) as error checking will be unable to confirm whether or not the computation is correct.
Cofactor compositeness testing: Suyama’s test
Suyama’s test is a Fermat probable primality test on the cofactor of a Fermat number. As a prerequisite, you must already have run a Pépin test, which should have saved a final residue as a file named e.g.
f23for a Pépin test of F23. Do not try to run a Suyama test as a single work type incorporating the preceding Pépin test.The
worktodoformat for the Suyama test is:Note that this work format uses the numeric value of 2m of a Fermat number Fm, rather than just the exponent m. At least one known prime factor must be supplied; composite factors are disallowed.
Prior to testing, Mlucas tries a “sanity check” on each known factor, which has the effect of testing whether the Pépin residue R has been correctly calculated. This calculation can be performed at any point up to the final iteration. More information is available here.
Pollard p–1 factoring
Work entries for p–1 factoring have two variations, however only the
Pminus1format is supported for Fermat numbers:The same note as regards the exponent for the Suyama test applies here also; supplying known factors is optional. The
-shift 0flag is again a necessary addition to the Mlucas command line.The testable Fermat numbers Fm = 22m + 1
The following table lists the default FFT lengths selected by Mlucas for the Fermat numbers in the range [14,33] and the known factors, required for some of the test types above.
"116928085873074369829035993834596371340386703423373313""1214251009,2327042503868417,168768817029516972383024127016961""825753601,188981757975021318420037633""31065037602817,7751061099802522589358967058392886922693580423169""13631489,81274690703860512587777""70525124609,646730219521,37590055514133754286524446080499713""4485296422913""64658705994591851009055774868504577""167772161""25991531462657,204393464266227713,2170072644496392193""76861124116481""151413703311361,231292694251438081""1766730974551267606529""2405286912458753""640126220763137,1095981164658689""46931635677864055013377""25409026523137"* These default FFTs selected by Mlucas have radices that cannot be used for Fermat modular squaring; thus F16 to F22 cannot be tested with Mlucas without overriding the default FFT selected, e.g.:
As mentioned under “Mlucas build notes” above, building Mlucas is highly architecture-specific, and some build types will not support all of the optimal FFT lengths. Finally, 4K appears to be the smallest usable FFT for the three smallest testable Fermat numbers.