View Single Post
Old 2022-05-13, 21:54   #82
ewmayer's Avatar
Sep 2002
República de California

2DDF16 Posts
Default F25-F30 cofactor status, Part 1

[I PMed a more-or-less-identical draft of this to Prime95, ATH; yorix, jasonp, philmoore and R. Gerbicz yesterday]

F25-F30 cofactor status:

In the context of testing the cofactor-PRP functionality which will be supported in Mlucas v21, I've at long last done Suyama-style PRP tests on the cofactors of F25-F30, using the Pépin-test residues I've generated for same over the past 10 years, as detailed in this thread - original primality-tests for F25-26 detailed in post #1 (recently updated with latest results), F27 in #2 and #5, F28 in #4 and #20, F29 in #29,#42,#52. For F30, the interim-residue files and logfile for the completed run @60 M FFT have been uploaded but the 99.5%-complete double-check run @FFT 64M is stalled due to my KNL having gone offline last week - I suspect the cheapie PSU installed by the vendor of this barebones system, but not yet had time to get under the hood, so to speak.

The cofactor-PRP results are tabulated in a "Part 2" followup to this note. My code only supports the Suyama cofactor-PRP method, which starts from the basic Pépin-test residue, does one mod-squaring to generate the Fermat-PRP residue A from that and an additional lg2(F) mod-squarings to generate the subtrahend B for the Suyama test, where F is the product of known prime factors; it makes little sense to spend roughly the same amount on a direct PRP test of such cofactors as needed by the Pépin test of F_m, only to have to re-do a similar amount of work when a new factor is discovered.

I first added some basic cofactor-PRP code to Mlucas in early 2018, and used it to test the cofactors of F25-29 using the Pépin-test residues I had generated via my primaiity tests for same. Did not post the cofactor-PRP results at the time because the accompanying Res64 values mismatched ones posted by Andreas Höglund (a.k.a. ATH), who had done cofactor-PRP tests of F25 and F26 using George's code. At the time I was trying to figure out why said result mismatched Andreas' value for what I thought was the same quantity, and in the ensuing PM exchange it did emerge that George's code-at-the-time (2009) which Andreas used in fact was doing a direct-PRP-test of the cofactor, but I was unaware of the cofactor-PRP runs for F25 and F26 done by forumite Yar (a.k.a. yorix - details below) in late 2017 using the then-latest Prime95 version. Having more pressing concerns at the time I decided to put that aside and revisit later. Mlucas v21 will have 2 major feature adds, PRP-CF and PRP-cert support, so in the context of the first, 'later' is now.

In 2009-2010 Andreas Höglund used George's code to test the cofactors of F25-27; cf. Posts #51, #62, #64 in this thread:
UID: athath, F25/known_factors is not prime. RES64: 44BFC8D231602007. Wd1: B9307E03,00000000
Known factors used for PRP test were: 25991531462657,204393464266227713,2170072644496392193

UID: athath, F26/76861124116481 is not prime. RES64: 6C433D4E3CC9522E.

UID: athath, F27/151413703311361/231292694251438081 is not prime. RES64: 481F26965DE16117.
Those posts were not clear on precisely what *type* of cofactor-PRP test was run - direct Fermat-PRP test on the cofactor C, or a Pépin-test (R = 3^((N-1)/2) (mod N)) of the Fermat number N = F*C followed by the Suyama postprocessing step (cf. the post by Phil Moore here), where one computes first the Fermat-PRP residue A = 3^(N-1) (mod N) = R^2 (mod N) via a single mod-squaring of the Pépin-test residue R, then uses the product of known factors F to compute B = 3^(F-1) (mod N), and checks if the difference (A - B) is divisible by the cofactor C. The Suyama version is preferable because it starts with a basic Pépin-test of the N, and as new factors are found that same residue can be used to quickly (#of squarings = bits in product-of-known-prime-factors) check each resulting cofactor for PRP-ness.

In late 2017 user Yar (don't know last name, uid = yorix) posted a thread about his own cofactor-PRP runs for F25-26, again using George's code, but now mentioning 2 different run types for each, which clarifies the types of cofactor-PRP tests used:
PRP test for F25 with known factors: PRP=N/A,1,2,33554432,1,"25991531462657,204393464266227713,2170072644496392193" gives 'composite' with res64: 7B6B087B84A45562

PRP test for F26 with known factors: PRP=N/A,1,2,67108864,1,"76861124116481" gives 'composite' with res64: FBB406B3A281838C
We see that Res64 differs from ATH's above - Yar notes "This test with base 3 and returns the same residue independent of the number of known factors", which indicates a Suyama-style cofactor-PRP test.

For F25 and F26 my Fermat-PRP Res64 values match Yar's for the Suyama-style cofactor check, and his direct-cofactor results match ATH's (though that is a same-software-used match). But it would be nice if someone using George's code could confirm not just the Fermat-PRP residues (A) for the above, but for purposes of pronouncing the ensuing cofactor-PRP results "cross-verified using independent codes", we should also cross-check the (A - B) mod C ones, where C is the cofactor. The Fermat-PRP computation of course constitutes the overwhelming bulk of a PRP-CF run, but it is important to also have assurance that the B-residue and (A - B) mod C have been correctly computed.

@George, would it be possible for you to tweak your code to print the Res64 checksum for the latter quantity? If Yar still has the Fermat-PRP-test residues from his runs of F25 and F26 using your code, it would then be a simple matter to rerun the Suyama step from those and cross-check the (A - B) mod C residues. If not, the F25 and F26 full-length tests are now easily runnable on modest hardware.

Also, is there a different Prime95/mprime worktodo-entry syntax for a direct-PRP test of a cofactor vs a 2-step approach (Fermat-PRP of N = F*C followed by Suyama step, or did you switch from the former to the latter along the way? Yar only echoes the workfile entry for the 2-step run, but notes that used 29.4 and then in a later post notes retrying with v29.3 and getting results matching Andreas' earlier ones.

Lastly, I did not see any post by Yar regarding a Suyama-style cofactor-PRP test for F27 using Prime95. It would be nice for someone to do such so we can put that one to bed, as well, at least until another factor is discovered. I could obviously do it myself, but I think the "different persons using different codes" optics would be better. Compute cost would be 20-30% more than a current GIMPS wavefront-PRP test.

Results for my Mlucas v21-prototype cofactor-PRP runs follow in Part 2.
ewmayer is offline   Reply With Quote