Fermat cofactors

[ewmayer]

[By way of cross-referencing]

I just posted details/results for my tests of the F25-F30 cofactors here. Executive Summary:

o My Fermat-PRP Res64 values (starting with my saved Pepin-test residues and doing one more mod-squaring) match Yar's, but we need George to tweak his code to also print the Res64 for the ensuing Suyama cofactor-PRP postprocessing step;

o Once we have the above added-Res64-print in place, it would be nice if someone could run Fermat-PRP/Suyama for F27 in order to cross-compare that one. Andreas Höglund did a PRP-CF run of F27 already some years ago, but George's code-at-the-time (2009) which Andreas used was doing a direct-PRP-test of the cofactor, whose results cannot be cross-checked against the Pepin+Suyama one.

[ATH]

Amazing work Ernst on those cofactor tests specifically the latter ones. You had the patience for those multiyear tests, as well as all the work on MLucas to make it happen.

I assume the "Fermat-PRP/Suyama" test of F27 is a type 5 PRP-CF test? I might run it if no one else does it, but not right now or the next few weeks. Maybe it is better to wait anyway in case George feels like and have time for this "tweak". It sounds from your description like it is a minor change/addition.

[ET_]

Thank you Ernst. It looks that the original page from Prof. Keller will be updated, once we have all the checks done.

Please keep us informed!

[ewmayer]

Originally Posted by ATH

Amazing work Ernst on those cofactor tests specifically the latter ones. You had the patience for those multiyear tests, as well as all the work on MLucas to make it happen.

I assume the "Fermat-PRP/Suyama" test of F27 is a type 5 PRP-CF test? I might run it if no one else does it, but not right now or the next few weeks. Maybe it is better to wait anyway in case George feels like and have time for this "tweak". It sounds from your description like it is a minor change/addition.

Thanks, Andreas (and Luigi).

Yes, 'type 5' is the GIMPS jargon - same as type 1, i.e. a Fermat-PRP, a^(N-1) (mod N), but followed by the Suyama-style cofactor-PRP step. The checksum-for-Suyama-result is a more or less trival code-modification, but crucial for cross-validation of cofactor-PRP results. I sent George (and AaronB and JamesH) email a few weeks ago suggesting that the JSON result format for PRP-CF be modified from simply noting 'C' or 'P' for the cofactor to including the Suyama-step Res64 for the 'C' cases, i.e. the vast majority. The preceding much-longer Fermat-PRP test of N could be reported separately, same as a regular PRP, and allowing all the same checks, i.e. Gerbicz and even proof/cert.

(It would be really cool to also support upload of Fermat-PRP residues to the server, because that would allow really fast server-side auto-running of the cofactor-PRP step for N where future deeper factoring work turns up a factor.)

[Gary]

The Fermat number status page http://www.prothsearch.com/fermat.html compiled by Wilfrid Keller has now been updated to reflect the Fermat cofactor proofs that have been performed over the last several years. During the past month or so, Wilfrid and I collaborated on a study to determine the appropriate updates for the “Factorizations known to be incomplete” and “Largest cofactors known to be composite” sections. For those who might be interested, here is an overview of our investigation.

For each Fermat number and Fermat cofactor from F20 to F30, to determine the earliest prover(s) of compositeness along with the “Proof Strength” that has been achieved by all provers to date, we reviewed the related mersenneforum threads, the Math Comp papers for F20, F22 and F24 primality testing, and the relevant emails from Wilfrid’s extensive email archive. For each early or new-data-providing proof report found, the Who, When, Program, Test Type, and all the Res64 and Selfridge-Hurwitz residues reported were captured in the attached spreadsheet table, organized by Fermat number and then Test Type. We noticed that there was a lot of variation in which residues and how many bits of each residue were reported by different researchers. Additionally, on a few rows the Notes column provides a summary of how the number was tested, including when different hardware and software were used. In the Who (Earliest) column, Bold is used to indicate the earliest compositeness prover found for each Fermat number or Fermat cofactor.

To try to categorize how rigorous of a proof of compositeness exists for each Fermat number or Fermat cofactor, a “Proof Strength” column was added. Proof Strength is a credibility grade based on all the proofs performed to date. The grade is determined by the best set of proofs (at least two) run by the same or different researchers producing matching residues. The grades are as follows:

• A indicates matching residues (at least Res64) covering the bulk of the calculations were produced using different hardware running different software, including different math libraries.
• B indicates matching residues (at least Res64) covering the bulk of the calculations were produced using different hardware running the same software with different configurations, such as different FFT lengths.
• C indicates matching residues (at least Res64) covering the bulk of the calculations were produced using different hardware running the same software with the same configuration.
• An extra “+” indicates matching Res 64 and Selfridge-Hurwitz residues exist for the final residue: Pepin for F20 and F24; Type 1 or Suyama for the cofactors.

For each Fermat number or Fermat cofactor in the table, the individual proofs that determine the Proof Strength are highlighted in blue or green. Note that sometimes the set of proofs that determine the Proof Strength do not include the earliest proof, such as with F25, F26 and F27.

In order to try to match and verify as many of the varied reported residues as possible, I wrote a companion program for mprime/Prime95 named “cofact”. Cofact uses the gwnum library, so does not qualify as “different software” than mprime. Cofact can be run in one of three “modes”:

1. Test a Fermat number for primality using the Pepin test. Then, if known factors are provided, use the Pepin residue to perform the Suyama PRP test on the cofactor.
2. Perform all steps in mode 1. Also compare the Suyama A residue calculated by cofact to the A residue read from the proof file generated by mprime when testing the same cofactor.
3. Read the Suyama A residue for a Fermat number from the mprime proof file (assumes it is correct), then perform the Suyama PRP test on the cofactor.

Cofact prints Res64 and Selfridge-Hurwitz (SH) residues for the Pepin residue (except in mode 3 where the Pepin residue is not available) and for the Suyama residues A, B and (A – B) mod C (following the same methodology and terminology as Ernst used with Mlucas). This enables comparison of cofact’s residues with the residues reported by other researchers, except for the Type 1 tests where the PRP test is done directly on the cofactor. So far, cofact has been run on all Fermat numbers F2 – F27. For F2 – F16, as a quick sanity check, cofact in mode 1 correctly reports each Fermat number or Fermat cofactor as prime or composite (residues from another program were not compared). For F17 – F26, cofact in mode 2 generates a full Suyama A residue that matches the full A residue in the mprime proof file.

For F20 – F26, I added the Pepin and Suyama Res64 and SH residues reported by cofact in mode 2 to the spreadsheet table. Above F26, cofact is only about 60% of the speed of mprime, even though it uses the same gwnum library as mprime (mprime is constantly tuning the gwnum algorithms used for best performance). So it is more time efficient to use mprime to generate the proof file with the A residue and then to use cofact in mode 3 to finish the Suyama test and report all the residues. Also, mprime has several advantages over cofact for long runs, including performing Gerbicz error checking and creating periodic checkpoint files to enable resumption after a system crash or power outage. So for F25 – F27 I added the Suyama residues reported by mprime+cofact mode 3 to the table (overlapping F25 – F26 as a cross check), along with placeholders for F28 and F29.

So far, all Res64 and SH residues reported by cofact or mprime+cofact match the residues or partial residues reported by other researchers. This is as expected, of course, but good to see anyway. In a few cases, the cofact or mprime+cofact test improved the Proof Strength grade. Here are the grades and a few comments about each of the Fermat numbers and cofactors:

• F20: A+. Young and Buell used two different Cray systems but the same Cray FFT math library. The cofact run was on a third different system using a different program and math library (gwnum), so improved the grade from A to A+.
• F21: A. In their F22 paper, Crandall et al. used different systems and different programs to test the cofactors of F19 and F21. For the Pepin test, they reported the SH residues (including mod 2^36 instead of mod 2^64 (Res64)). For the Suyama test they reported two 16 bit residues that can be used to calculate the 16 LSBs of the final Suyama residue (A – B) mod C, which cofact matches. Our grade of A reflects that matching final Suyama Res64 and SH residues from different programs do not exist yet.
• F22: A. Domanov and Yamada got matching Type 1 Res64 using different hardware and programs, but no SH residues were reported. No set of Type 5 tests earning an A+ exists yet since all tests have been with mprime/Prime95 or cofact, both of which use the gwnum library.
• F23: A. No residues for the F23 cofactor test were reported in the F24 paper. However, an email exchange between Ernst Mayer, Richard McIntosh and Wilfrid Keller provided Res64 and SH residues for the Pepin test, and Res64 for the Suyama A step, but not final Suyama residues. The two Pepin tests were performed by Ernst Mayer and by Jason Papadopoulos using independently developed programs on different hardware, and completed in November 2000. Richard Crandall then performed the Suyama test using the matching Pepin residue.
• F24: A+. Crandall et al. used three different systems running two different programs, and reported Res64 and SH residues.
• F25 – F27: A+. Ernst Mayer’s Mlucas v21 prototype program reported Res64 for the Pepin test (and SH residues for F27), and Res64 and SH residues for each step of the Suyama test. Cofact matches all of these residues. Mlucas has an FFT library written by Ernst independently from George’s gwnum FFT library used in Prime95. So entirely different software is achieved, resulting in a Proof Strength of A+.
• F28 – F30: currently B+. Ernst tested each number twice with different hardware and the same software with different FFT lengths, resulting in matching Pepin residues. Also, F29 and F30 were mostly run on systems with ECC memory. So the chances of there being undetected hardware errors that caused identical errors in both final residues is almost zero. The use of two different FFT lengths provided some “different software” characteristics in the primary square/mod calculations. While there could be a bug in the “framework code” around the square/mod loop, the fact that Mlucas and mprime+cofact produced the same residues for F25 – F27 makes us think this is unlikely. So we concluded that B+ is a “passing grade” and that F28 – F30 should be included in the known composite sections on the Fermat number status page. Over the next few months, I plan to run mprime+cofact on F28 (mprime already 30% complete) and F29. Those residues will, hopefully, match Ernst’s Mlucas residues, raising those grades to A+. When trying to test the F30 cofactor, mprime v30.8b17 reports “PRP cannot initialize FFT code for F30, errcode=1002. Number sent to gwsetup is too large for the FFTs to handle.” So the F30 grade will remain B+ for now.

I investigated using Mlucas to test F21 – F23 to bump their grades up to an A+. But apparently the Mlucas v21 prototype code that Ernst used for F25 – F30 is the first version with the Suyama test implemented, and it does not appear that he ever released v21. If anyone has Mlucas v21 and can test the F21 – F23 cofactors, we would love to see the results.

Finally, please let me know if you are aware of any compositeness proofs earlier than the ones reported in the spreadsheet, or if you have additional information on the ones reported. Thanks!

[Andrew Usher]

Thank you! Though my e-mail wasn't answered, my concerns have been addressed - no one again will think that F22 needs verification, and proper credit is given to Ernst Mayer for his checking and double-checking the larger cofactors. I'd only suggest that perhaps the table 'Composite ... without known factor' should also have 'Earliest prover' instead of 'prover', for consistency and accuracy: it's so easy to check those again with prime95/mprime that many must have done so (indeed I just did F20 to show this).

I have to correct you on F30: from what I know it, as well as 28 and 29, can and should be verified with prime95/mprime, but AVX-512 is required at that FFT size (otherwise an FFT error similar to that you reported would be expected). It is still, of course, rather a long test even there.

Last could you add to this brief definitions of all these terms for the benefit of us that have experience only with prime95 in this context?

[Gary]

Originally Posted by Andrew Usher

... I'd only suggest that perhaps the table 'Composite ... without known factor' should also have 'Earliest prover' instead of 'prover'.

I have to correct you on F30: from what I know it, as well as 28 and 29, can and should be verified with prime95/mprime, but AVX-512 is required at that FFT size (otherwise an FFT error similar to that you reported would be expected). It is still, of course, rather a long test even there.

Last could you add to this brief definitions of all these terms for the benefit of us that have experience only with prime95 in this context?

Good suggestion. The "Composite Fermat numbers Fm without known factor" table now lists "Earliest prover".

Interesting point about AVX-512, which none of my systems have. mprime runs fine on the F28 and F29 cofactors on my AVX2 systems, but throws the error I mentioned on F30. Experimenting with Mersenne numbers, it looks like my systems can run 900M but not 960M, so the limit is somewhere between. What is the maximum exponent that the latest mprime supports without and with AVX-512? I poked around in the mprime readme files and on the forum but could not find recent maximums.

Let me know which terms need a brief defintion and I can add them.

Originally Posted by cxc

I would be most interested in having a look at your cofact add-on, seeing as I saved proofs for the PRP runs on F17 to F26, generated by mprime 30.10; as a ‘sanity check’, I gather these ought to return the additional values I was after, by using cofact’s mode 3, which hopefully match the various residues in your spreadsheet. A Linux binary would be capital!

Of course in the long term, should another prime factor turn up for any of these smaller Fermats for which Pépin residues were obtained, something like cofact would be most useful for seeing whether the new factor helps complete the factorisation. (I know it’s unlikely, but one can dream.)

Attached is the C source code for cofact, along with a Makefile, Linux binary and output files for F25 to F27. On your Linux system you can extract it with "7z e cofact_v0.6.tar.7z" then "tar -xvf cofact_v0.6.tar". Running "cofact -h" will provide a list of the command line options. Assuming you have an mprime proof file for F25 (for example), you can run cofact in mode 3 as follows:

> cofact -upr F25.proof 25 25991531462657 204393464266227713 2170072644496392193

Program to check the primality of a Fermat number and it's cofactor: cofact, Version 0.6 (Jun  2 2023 11:42:45)
Run started: Friday 02 June 2023 11:43:59

Command line: cofact -upr F25.proof 25 25991531462657 204393464266227713 2170072644496392193

Reading residue from proof file: F25.proof
Proof file description: (F25)/25991531462657/204393464266227713/2170072644496392193

Using A residue from proof file instead of calculating it
Skipping the Pepin test

Testing the F25 cofactor for primality using the following known factors: 25991531462657 204393464266227713 2170072644496392193
Cofactor is 10100842 digits long
A Residue mod 2^64 2^35-1 2^36-1 2^36: 0x7B6B087B84A45562 26994100025 66886679148 49470002530
B Residue mod 2^64 2^35-1 2^36-1 2^36: 0x2909830729BFA110 30348546187 21153567739 30765195536
(A-B) mod C Residue mod 2^64 2^35-1 2^36-1 2^36: 0x7A551893ACF4BE4E 34178045549 65496009072 15786622542
F25 cofactor is composite

Run ended: Friday 02 June 2023 11:46:46, Wall time = 0:02:46 (HH:MM:SS)

Yes, if you generate and save mprime proof files for F17 - F29, then if/when the next factor is found for any of those Fermat numbers you can test the new cofactor in just a few minutes.

[R. Gerbicz]

Originally Posted by Gary

if you generate and save mprime proof files for F17 - F29, then if/when the next factor is found for any of those Fermat numbers you can test the new cofactor in just a few minutes.

You can do this even when you saved only a truncated residue (using say 2048 bits), are you using this?
See my method:
https://mersenneforum.org/showthread.php?t=23462

ps. Basically this is weaker than a probable prime test, but its error rate is still very small if d is smaller than 2048 bits.

[Andrew Usher]

Originally Posted by Gary

Interesting point about AVX-512, which none of my systems have. mprime runs fine on the F28 and F29 cofactors on my AVX2 systems, but throws the error I mentioned on F30. Experimenting with Mersenne numbers, it looks like my systems can run 900M but not 960M, so the limit is somewhere between. What is the maximum exponent that the latest mprime supports without and with AVX-512?

About right, it should be a little over 920M for AVX2 (1169M for AVX-512). I don't have the kind of technical knowledge to answer exactly, but the limit is set in terms of FFT size, not exponent itself, and Mersenne numbers should be the best case for the type of FFT being used. But the Fermat numbers are so far apart the only difference is the limit is F30 for AVX-512 (shown e.g. by this P-1 result: https://mersenneforum.org/showpost.p...3&postcount=17) and F29 otherwise.

For help getting access to AVX-512, Ken Kriesel might be the best guy to talk to here.

I poked around in the mprime readme files and on the forum but could not find recent maximums.

As they are determined by the mathematics of FFT, they will not normally change more than very slightly with version.

Let me know which terms need a brief defintion and I can add them.

Well, what was in my mind was the different types of residues and of cofactor test, and what if anything they correspond to in Prime95 terminology. Especially, what you mean by 'Selfridge-Hurwitz' residues (the mod 2^35-1, 2^36-1, 2^36 I think) and by 'Suyama' tests, the latter of which seems to cover any cofactor test including the type you added with the cofact application.

[Gary]

Originally Posted by R. Gerbicz

You can do this even when you saved only a truncated residue (using say 2048 bits), are you using this?
See my method:
https://mersenneforum.org/showthread.php?t=23462

ps. Basically this is weaker than a probable prime test, but its error rate is still very small if d is smaller than 2048 bits.

I am currently using the full A residue, which is the first thing after the header in the proof file. Thanks for the link to the other method. I'll check it out.

[cxc]

To Gary: thanks very much for cofact! All of my proofs for F17 to F26 (which are uploaded here), agree with the values you posted the day before yesterday (except for F24 which is still running). I’ve attached my results here using the spreadsheet format you provided, which clarifies which version of mprime I was using (30.10 for the most part).

To Andrew: in Prime95 parlance, the Pépin residue is described as type 2 in undoc.txt; I have a set of these residues for F17 up to F23, which also happen to match the values that previous testers in Gary’s spreadsheet had found. The Selfridge-Hurwitz residues were used for error-checking their computations as machine errors were frequent, and converting the last 9 hex digits of RES64 to decimal gives the residue modulo 2^36; apart from that correspondence I don’t think there’s any other matching terminology (I’m sure you must already know this?).

To Robert: that’s a very nice trick using the RES2048 residue (or other suitably large residue) – chapeau!