Fermat cofactors

[kriesel]

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? I poked around in the mprime readme files and on the forum but could not find recent maximums.

In the reference info compilation, there's a post for mprime/prime95 exponent limits. Inspecting the source code can give the exact limits versus instruction set. And there's a lengthy post about limits and considerations for large exponents, of multiple applications. Mlucas may suit your hardware better.

[cxc]

Compilation note for cofact 0.6:
Gary’s code assumes an older version of gwnum (29.8), so if you have the gwnum included in the p95v30.8 source (as I did) then there are two modifications required, at lines 387 and 436 of cofact.c:

gwsquare2 (&gwdata, r_gw, r_gw, 0);

For Ken: although Mlucas may handle F30 better, one of the requirements for the “A+” level of certainty is using different software with different maths libraries to obtain the same result, hence investigating Prime95/mprime rather than Mlucas.

[cxc]

I have a question … (and one other, very trivial bug fix for cofact 0.6)

For those who would prefer to TL,DR the question is, who was doing cofactor compositeness tests in the 80s?

As for the bug, see below.

After seeing that there was a new factor, I noticed Professor Keller’s Fermat factor page has dropped the information about provers of the composite cofactors of F₁₂ to F₁₉, now that it’s showing up to F₃₀ — and all due credit to him for recognising the epic work done by Ernst W. Mayer. And previously, it had simply described the provers for the c₁₁₃₃ | F₁₂, c₄₈₈₀ | F₁₄, c₃₉₃₉₅ | F₁₇, and c₁₅₇₇₇₀ | F₁₉ cofactors as being anonymous, when it seems even a minimal amount of effort could have furnished at least one name, for each of these, if not more:

c₁₁₃₃ | F₁₂: M. Vang, S. Batalov, et al.
c₄₈₈₀ | F₁₄: W. B. Lipp, R. D. Silverman, and T. Rajala
c₃₉₃₉₅ | F₁₇: D. Chia and T. Sorbera (and possibly A. Höglund?)
c₁₅₇₇₇₀ | F₁₉: A. Kruppa (as well as ‘J. R. K.’)

L. Morelli still has the full list at http://www.fermatsearch.org/factors/composite.php but “Different anonymous provers” “Various different provers” etc. etc. for the provers of these four cofactors.

Feeling slightly unsatisfied, I poked around in the literature a bit to dig up the historical Pépin tests (from Morehead and Western onward) to see how often these compositeness tests were done in light of a new factor discovery, and to examine the chronology:

Pre-computers:
1905: F₇ is composite, no factors known (Morehead and Western, independently!)
1909: F₈ is composite, ditto (Morehead and Western together, splitting the effort between them)

Start of the computer age:
1952: F₁₀ is composite, no factors known yet (Robinson on SWAC, also confirming F₇ and F₈ were done correctly without computers)
1960: F₁₃ is composite, ditto (Paxson, also confirming F₇, F₈, and F₁₀)
1961: F₁₄ ditto (Hurwitz and Selfridge, confirming F₇, F₈, F₁₀, and F₁₃, and publishing S–H residue triplets for each of these except F₁₀ in their 1964 paper)

1967: c₁₄₈ | F₉ & c₂₉₁ | F₁₀ cofactors are composite (Brillhart – see the 1975 Hallyburton & Brillhart paper announcing a new factor for F₁₂ and the first for F₁₃)

ca. 1978?–79: c₆₀₆ | F₁₁, c₁₂₀₂ | F₁₂, & c₂₄₅₄ | F₁₃ are composite (Wagstaff – see Gostin’s 1980 paper on F₁₇)

1984: c₉₈₅₆ | F₁₅ is composite (Suyama – but it is very difficult to get this abstract, or Suyama’s later one)
1986: c₁₁₈₇ | F₁₂ (Baillie, after finding the 5th factor, but did not find a citation)
1987: c₉₈₄₀ | F₁₅ (Suyama again, but even more difficult than his previous to find information on this result)
1987: c₃₉₄₄₄ | F₁₇ (also Baillie, again did not find a citation)
1987: F₂₀ is composite (Young & Buell)

...
So by 1992, Lenstra, Manasse et al. report the following cofactors to be composite in their F₉ factorisation paper, but without attribution:
c₂₉₁ | F₁₀ (Brillhart); c₁₁₈₇ | F₁₂ (Baillie); c₂₄₁₇| F₁₃ (?); c₉₈₄₀ | F₁₅ (Suyama?); c₁₉₇₂₀ | F₁₆ (?); c₃₉₄₄₄ | F₁₇ (Baillie?); c₇₈₉₀₇ | F₁₈ (?)
...

1993: c₁₅₇₈₀₄ | F₁₉, c₆₃₁₃₀₆ | F₂₁, & F₂₂ are composite (Crandall, Doenias, Norrie & Young, who also provide S–H triplets for Pépin tests on each of the eighteen composite Fermat numbers F₅ – F₂₂)
1993: F₂₂ is composite (Trevisan & Carvalho obtain same result, independently of CDNY)
1995: c₂₃₉₁ | F₁₃ is composite (Brent)
1995: c₁₉₆₉₄ | F₁₆ is composite (Brent & Crandall – not Brent alone. Their 2000 paper is clear they tested independently, to verify one another’s results: “using different programs on different machines in different continents”! They also cite compositeness of the previous cofactors without attribution.)
1997: c₉₈₀₈ | F₁₅ (Brent & Crandall likewise)
1999: c₇₈₈₈₄ | F₁₈ (Crandall)
1999: F₂₄ is composite (Crandall, Mayer & Papadopoulos)
2000: c_2525215 | F₂₃ (also Crandall, Mayer & Papadopoulos)

And then we reach the GIMPS era, already covered.

So there were at least three question marks and several other assumptions in-between Brillhart 1967/1975 and the CDNY paper on F₂₂ in 1993. It doesn’t entirely surprise me that these are mostly around the 1980s (in other fields it can be really awkward to search in the pre-digitisation era), even though this is living memory for a lot of people.

So looking at the question marks:

c₂₄₁₇ was the then-known cofactor after Crandall had found 2 factors of F₁₃ in 1991. Surely he would have tested it for compositeness? And if not him, then someone like Brent who he collaborated with?

c₁₉₇₂₀ | F₁₆ and c₇₈₉₀₇ | F₁₈ had had one factor discovered before, by Selfridge in 1953 and Western circa 1903 respectively. Would Suyama have checked these cofactors after having looked at c₉₈₅₆ | F₁₅ in 1984 (and again)?

Yes, I totally realise these cofactor compositeness results are highly ephemeral, that they fall out of date as soon as a new factor shows up, and that these days we can replicate the work in seconds that once took hours or months of calculations; however, it is a part of the history of investigating these numbers.

Speaking of history, cofact nicely replicated all of the prior results I could lay my hands on, back to 1905, where a residue of some sort had been published: Morehead & Western’s F₇ & F₈; Robinson’s funky F₁₀ hex residue (using u to z as the hex digits!); S–H; Young & Buell; CDNY; and Crandall, Mayer & Papadopoulos. Only one error was found among them (the F₁₂ 2^35 – 1 residue in CDNY is missing the first digit, 5, but is otherwise correct). cofact however did throw some weird gwsetup errors and one trivial bug trying to run a Pépin test on F₀, since the test won’t work on n = 0, so here’s a little fix.

    if (n == 0) {
        printf ("Error: the Pepin test cannot be run on Fermat number F0.\n\nF0 = 3 is prime!\n");
        exit (1);
    }

... around line 301 (just before incrementing argi++ in the loop parsing the Fermat number) should do the trick.

[Batalov]

I remember that I ran a lot of GFN(n,b) and GFN'(n,odd b) cofactor compositeness tests, as well, up to n<=30,31 but they were never recorded. If any of them would have been PRP, - that would have been interesting and would have made the news, but composite - you just write that computation off. This is like writing into history books that Jon B. Worrysome (or insert any other name) on March 19th, 2012 accurately predicted that the sun will come up again tomorrow in the east. That is, arguably, for n<30 (adjusted for the century; for 1952, criteria are different). Above 30, there are a few n values where this result is possible to obtain with a lot of effort which deserves to be recorded. And above 35-36, again, we enter the uncharacterized.

(OTOH, I did nothing to write home about for F12. It was all Mike.)

[cxc]

Hi Serge, thanks! Your point about the recency of results is well taken. Almost anyone and his or her desktop computer could have checked the most recent cofactors for m < 24 from 2009 onward. But going back to last century, it’s a very different story. The S–H paper in 1964 offers a set of punched cards for anyone willing to try to do Pépin’s test on the next uncharacterised Fermat (at that point it was F₁₇) and helpfully they published their interim residue at the 20th of 131,071 squarings!

By the same token, the 1980s feels like it ought to be recent enough to be in people’s memories; and results still took a long time to achieve even then. I found a paper from 1990 replicating the Suyama F₁₅ cofactor computation where he manages to do it in 11 hours (where Suyama had taken over a hundred, six years before). My eight-year old Mac now takes 1 second, so hooray for progess?

[Batalov]

Originally Posted by cxc

By the same token, the 1980s feels like it ought to be recent enough to be in people’s memories; and results still took a long time to achieve even then.

In 1980 actually, I computed 100,000 and later 200,000 decimal digits of 𝜋, which is now of course a fraction of a second to do. But for a schoolchild, it was an ok achievement.

I coded everything myself from scratch (in Algol, too, iirc), but it was run at the USSR Nuclear Center as a test program on spare compute bandwidth by my father (pretending to have written it as a test of hardware. Don't tell anyone but he never learned Algol, only Fortran). In fact, I might still have the stack of perfocards. My father decades later gifted it back to me.

[Andrew Usher]

Originally Posted by Batalov

I remember that I ran a lot of GFN(n,b) and GFN'(n,odd b) cofactor compositeness tests, as well, up to n<=30,31 but they were never recorded.

I assume you mean 20-21, not 30-31 - a GF is bigger than the ordinary Fermat of the same n, and testing something the size of F30 back then would have been very noteworthy!

It's strange that no one ever did run the Pepin test on F17 - with long multiplication, it would be ~64 times the effort of F14, and computers 64 times faster than a 7090 were not rare by the time the factor was found in 1978.