Fermat Cofactor Study

By Gary Gostin

May 31, 2023

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!

Addendum March 4, 2024

After the initial report above was published, the following additional work was performed by various individuals:

• 2023-08-14: I finished the test of F28 using mprime + cofact and confirmed that the cofactor is composite. This also verified all of the Res64 and SH residues that Ernst generated using Mlucas. This increased the proof strength of F28 to A+.
• 2023-11-01: Ryan Propper finished testing F29 using mprime + cofact and confirmed that the cofactor is composite. This test took approximately two and a half months. This test also verified all of the Res64 and SH residues that Ernst generated using Mlucas. This increased the proof strength of F29 to A+.
• 2024-03-01: Catherine Cowie and Teal Dulcet resurrected the Fermat cofactor testing code in Mlucas. Catherine then ran this test on F21, F22 and F23, generating the same Res64 and SH residues as cofact. This increased the proof strength of F21, F22 and F23 to A+.

The residues for all of the above tests and resulting A+ proof strengths have been added to the updated spreadsheet table.