mersenneforum.org Pépin tests of Fermat numbers beyond F24
 Register FAQ Search Today's Posts Mark Forums Read

2020-01-25, 20:52   #78
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

112×13 Posts

Quote:
 Originally Posted by ewmayer @Jeppe: This is simply the basic Pépin residue ... (And also one wants the 2nd double-check run at the slightly larger FFT length to finish and confirm the Pépin-test results.)
Have you checked that:
(3^(2^(2^m)) mod F_n) mod q = 3^(2^(2^m)) mod q
is true for the stored interim residues?

Since you have 3^(2^(2^m)) mod F_n then to get the left side is trivial and you can get quickly the right side, becuase q is small , the check is cheap. Though it is not that very-very strong check, but the two known factors could find a mismatch with probability = 1-(1e-10) which is still quite impressive. Note that we don't get the strength of 1/(q-1) or 1/znorder(Mod(3,q)) because the order is divisible by a "large" power of two, and that will be lost in the iterated squarings of a wrong residue.

Last fiddled with by R. Gerbicz on 2020-01-25 at 20:54 Reason: small typo

2020-01-27, 21:41   #79
ewmayer
2ω=0

Sep 2002
República de California

23×32×163 Posts

Quote:
 Originally Posted by R. Gerbicz Have you checked that: (3^(2^(2^m)) mod F_n) mod q = 3^(2^(2^m)) mod q is true for the stored interim residues? Since you have 3^(2^(2^m)) mod F_n then to get the left side is trivial and you can get quickly the right side, becuase q is small , the check is cheap. Though it is not that very-very strong check, but the two known factors could find a mismatch with probability = 1-(1e-10) which is still quite impressive. Note that we don't get the strength of 1/(q-1) or 1/znorder(Mod(3,q)) because the order is divisible by a "large" power of two, and that will be lost in the iterated squarings of a wrong residue.
ITYM (3^(2^(2^m - 1)) mod Fm) mod q = 3^(2^(2^m - 1)) mod q, since the Pépin test is just an Euler-pseudoprime test (which happens to prove rigorous in the special case of the Fm), i.e. computes 3^(2^((Fm - 1)/2)) mod Fm = 3^(2^((2^m)/2)) mod Fm. But in any event, that's a good suggestion - fiddled my code to load the final Pépin-test residue R from the savefile and for the 2 known small prime factors p=640126220763137 and q=1095981164658689 computed

R == 367500396407933 (mod p) and
R == 95971534699540 (mod q).

I then separately computed 3^(2^(2^m - 1)) mod p and q via (2^m-1) = 1073741823 iterated squarings modulo p and q, separately, and the results match, which anyone can confirm on even quite modest hardware. So we have quite good confidence in the result, on top of the 2 runs agreeing through ~740 Miter (as of the latest 64M-FFT run update from Ryan), and said runs being done on high-end server ssytems with ECC memory.

For F31 I will also be using the now-famous periodic whole-residue check named in honor of the above-quoted forum member. :)

Last fiddled with by ewmayer on 2020-01-27 at 21:43

2020-01-28, 08:49   #80
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

112×13 Posts

Quote:
 Originally Posted by ewmayer I then separately computed 3^(2^(2^m - 1)) mod p and q via (2^m-1) = 1073741823 iterated squarings modulo p and q, separately, and the results match, which anyone can confirm on even quite modest hardware.
Trivial note: it is faster to reduce the exponent mod (p-1) [use Fermat's little theorem].

2022-05-13, 21:54   #82
ewmayer
2ω=0

Sep 2002
República de California

101101110110002 Posts
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:
Quote:
 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:
Quote:
 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.

2022-05-13, 22:05   #83
ewmayer
2ω=0

Sep 2002
República de California

23×32×163 Posts
F25-F30 cofactor status, Part 2

In each case I begin with a quick Pépin-test residue sanity check, summarized here:
Quote:
For PRP-tests of N with known-factors (e.g. prelude to a cofactor-PRP postprocessing step),
R. Gerbicz [post #79 of https://mersenneforum.org/showthread...=18748&page=8] suggests, using
the specific case of the (m)th Fermat number F_m to illustrate:
Quote:
 Have you checked that: (3^(2^(2^m)) mod F_m) mod q = 3^(2^(2^m)) mod q is true for the stored interim residues? Since you have 3^(2^(2^m)) mod F_n then to get the left side is trivial and you can get quickly the right side, becuase q is small , the check is cheap. Though it is not that very-very strong check, but the two known factors could find a mismatch with probability = 1-(1e-10) which is still quite impressive. Note that we don't get the strength of 1/(q-1) or 1/znorder(Mod(3,q)) because the order is divisible by a "large" power of two, and that will be lost in the iterated squarings of a wrong residue.
(For Pépin-test residue, we'd actually check (3^(2^(2^m - 1)) mod F_m) mod q = 3^(2^(2^m - 1)) mod q.)
More generally, for the powermod residue R = a^pow (mod N) where N has prime factor q, we check whether

a^pow (mod N) = a^pow (mod q).

If pow > q, the RHS can be simplified using Fermat's little theorem, a^(q-1) == 1 (mod q), thus
a^pow == a^pow' (mod q), where pow' = pow (mod q-1).

Example: For the final Pépin-test residue R for F30 (N = 2^2^30 + 1, pow = (N-1)/2 = 2^(2^30 - 1)), with
2 known small prime factors p = 640126220763137 and q = 1095981164658689, we get

p: pow' = 2^(2^30 - 1) (mod p-1) = 433448099512320, R == 367500396407933 (mod p)
q: pow' = 2^(2^30 - 1) (mod q-1) = 96576634617856, R == 95971534699540 (mod q).
In the results below, for each prime factor, 'A: R == ' is the full residue (mod p) and 'B: R ==' is the (mod p) squaring-chain checksum computed as above.

For all the key quantities I give the "enhanced Selfridge-Hurwitz residue" triplet, which consists of residues mod 2^64 (hex), 2^35-1 and 2^36-1, the latter two printed in decimal form. Lastly, I computed GCD(A - B,C) to check whether each cofactor is possibly a prime power, as described in Phil Moore's Part-1-linked post [or cf. Crandall & Pomerance (2nd ed.), exercise 4.8]. Unsurprisingly, all cofactors come up "composite", and even more unsurpisingly, none is a prime power:
Code:
F25: (I also re-ran @2048K FFT and confirmed the same values):
Computing 33554431-squaring residue R (mod known prime q = 25991531462657)
A: R == 5785371429337 (mod q)
B: R == 5785371429337 (mod q)
Computing 33554431-squaring residue R (mod known prime q = 204393464266227713)
A: R == 45685916416586703 (mod q)
B: R == 45685916416586703 (mod q)
Computing 33554431-squaring residue R (mod known prime q = 2170072644496392193)
A: R == 991358595838356746 (mod q)
B: R == 991358595838356746 (mod q)
F25: using FFT length 1792K = 1835008 8-byte floats.
this gives an average   18.285714285714285 bits per digit
Doing one mod-F25 squaring of iteration-33554431 residue [Res64 = CB913B6E3B1FFE2A] to get Fermat-PRP residue
Fermat-PRP residue (A)     = 0x7B6B087B84A45562,26994100025,66886679148
Processed 162 bits in binary modpow; MaxErr = 0.203125000
3^(F-1) residue (B)        = 0x2909830729BFA110,30348546187,21153567739
(A - B) Res64 = 0x526185745AE4B453, C Res64 = 0x21CC1C03F0000001
(A - B)/C: Quotient = 10040206794592865905247433568023540557761720874501, Remainder Res64 = 0x7A551893ACF4BE4E
Suyama Cofactor-PRP test of F25 / 25991531462657 / 204393464266227713 / 2170072644496392193 with FFT length 1835008 = 1792 K:
(A - B) mod C has Res64,35m1,36m1: 0x7A551893ACF4BE4E,34178045549,65496009072.
This cofactor is COMPOSITE [C10100842]. Checking prime-power-ness via GCD(A - B,C) ...
GCD((A - B)[33554304 bits], C[33554270 bits]) = 1
Time for GCD = 00:00:10.857
Cofactor is not a prime power.

F26: (I also re-ran @4096K FFT and confirmed the same values):
Computing 67108863-squaring residue R (mod known prime q = 76861124116481)
A: R == 10772922302714 (mod q)
B: R == 10772922302714 (mod q)
F26: using FFT length 3584K = 3670016 8-byte floats.
this gives an average   18.285714285714285 bits per digit
Doing one mod-F26 squaring of iteration-67108863 residue [Res64 = 2B58BDE2A0C14045] to get Fermat-PRP residue
Fermat-PRP residue (A)     = 0xFBB406B3A281838C, 2193939191, 7371940776
Processed 46 bits in binary modpow; MaxErr = 0.187500000
3^(F-1) residue (B)        = 0x25F5AB0FFC728C87,32173443562,20444894301
(A - B) Res64 = 0xD5BE5BA3A60EF705, C Res64 = 0x23FFBA1860000001
(A - B)/C: Quotient = 49561426973911, Remainder Res64 = 0xB7BD14979ACF222E
Suyama Cofactor-PRP test of F26 / 76861124116481 with FFT length 3670016 = 3584 K:
(A - B) mod C has Res64,35m1,36m1: 0xB7BD14979ACF222E, 6416457631,15466936163.
This cofactor is COMPOSITE [C20201768]. Checking prime-power-ness via GCD(A - B,C) ...
GCD((A - B)[67108864 bits], C[67108818 bits]) = 1
Time for GCD = 00:00:25.555
Cofactor is not a prime power.

F27: (I also re-ran @7.5M and 8M FFT and confirmed the same values):
Computing 134217727-squaring residue R (mod known prime q = 151413703311361)
A: R == 36549260191848 (mod q)
B: R == 36549260191848 (mod q)
Computing 134217727-squaring residue R (mod known prime q = 231292694251438081)
A: R == 68921389296064753 (mod q)
B: R == 68921389296064753 (mod q)
F27: using FFT length 7168K = 7340032 8-byte floats.
this gives an average   18.285714285714285 bits per digit
Doing one mod-F27 squaring of iteration-134217727 residue [Res64 = 043A6C8B9272B297] to get Fermat-PRP residue
Fermat-PRP residue (A)     = 0xC3B191C45CCD7820,21887650168,55240256170
Processed 104 bits in binary modpow; MaxErr = 0.281250000
3^(F-1) residue (B)        = 0x485F292142F953EC,20036545122,26481669619
(A - B) Res64 = 0x7B5268A319D42434, C Res64 = 0xD8C9BECF60000001
(A - B)/C: Quotient = 13668745121613830518711853822333, Remainder Res64 = 0x79E89190C56372B7
Suyama Cofactor-PRP test of F27 / 151413703311361 / 231292694251438081 with FFT length 7340032 = 7168 K:
(A - B) mod C has Res64,35m1,36m1: 0x79E89190C56372B7, 2608954171,29330680430.
This cofactor is COMPOSITE [C40403531]. Checking prime-power-ness via GCD(A - B,C) ...
GCD((A - B)[134217664 bits], C[134217624 bits]) = 1
Time for GCD = 00:00:59.492
Cofactor is not a prime power.

F28: (I also re-ran @16M FFT and confirmed the same values):
Computing 268435455-squaring residue R (mod known prime q = 1766730974551267606529)
A: R == 688455961638747199546 (mod q)
B: R == 688455961638747199546 (mod q)
F28: using FFT length 15360K = 15728640 8-byte floats.
this gives an average   17.066666666666666 bits per digit
Doing one mod-F28 squaring of iteration-268435455 residue [Res64 = 468731C3E6F13E8F] to get Fermat-PRP residue
Fermat-PRP residue (A)     = 0x7CAE1275B362B2CA,20461105324,30894284803
Processed 70 bits in binary modpow; MaxErr = 0.296875000
3^(F-1) residue (B)        = 0xBD496177DB5155A0,33633822046, 3778945069
(A - B) Res64 = 0xBF64B0FDD8115D2B, C Res64 = 0x39AEB33000000001
(A - B)/C: Quotient = 585290509330851034797, Remainder Res64 = 0x790BE051D73D667E
Suyama Cofactor-PRP test of F28 / 1766730974551267606529 with FFT length 15728640 = 15360 K:
(A - B) mod C has Res64,35m1,36m1: 0x790BE051D73D667E, 4159568998,55362539930.
This cofactor is COMPOSITE [C80807103]. Checking prime-power-ness via GCD(A - B,C) ...
GCD((A - B)[268435392 bits], C[268435386 bits]) = 1
Time for GCD = 00:02:16.895
Cofactor is not a prime power.

F29: (I also re-ran @32M FFT and confirmed the same values):
Computing 536870911-squaring residue R (mod known prime q = 2405286912458753)
A: R == 2364493566098202 (mod q)
B: R == 2364493566098202 (mod q)
read_ppm1_savefiles: Hit EOF in read of FFT-kblocks ... assuming a pre-v18 savefile.
F29: using FFT length 30720K = 31457280 8-byte floats.
this gives an average   17.066666666666666 bits per digit
Doing one mod-F29 squaring of iteration-536870911 residue [Res64 = BECE1E5FFBE5EC12] to get Fermat-PRP residue
Fermat-PRP residue (A)     = 0x9BD416DB3918C152,32748692453,58920206666
Processed 51 bits in binary modpow; MaxErr = 0.375000000
3^(F-1) residue (B)        = 0x30AFC6010F62884B, 7473784009, 6544795868
(A - B) Res64 = 0x6B2450DA29B63908, C Res64 = 0x3FF7746780000001
(A - B)/C: Quotient = 1671099484324226, Remainder Res64 = 0xAB3DBCEFFE907786
Suyama Cofactor-PRP test of F29 / 2405286912458753 with FFT length 31457280 = 30720 K:
(A - B) mod C has Res64,35m1,36m1: 0xAB3DBCEFFE907786,13349243207,41564307636.
This cofactor is COMPOSITE [C161614233]. Checking prime-power-ness via GCD(A - B,C) ...
GCD((A - B)[536870912 bits], C[536870861 bits]) = 1
Time for GCD = 00:05:09.784
Cofactor is not a prime power.

F30: (I also re-ran @64M FFT and confirmed the same values):
Computing 1073741823-squaring residue R (mod known prime q = 640126220763137)
A: R == 367500396407933 (mod q)
B: R == 367500396407933 (mod q)
Computing 1073741823-squaring residue R (mod known prime q = 1095981164658689)
A: R == 95971534699540 (mod q)
B: R == 95971534699540 (mod q)
F30: using FFT length 61440K = 62914560 8-byte floats.
this gives an average   17.066666666666666 bits per digit
Doing one mod-F30 squaring of iteration-1073741823 residue [Res64 = A70C2A3DB98D6D9D] to get Fermat-PRP residue
Fermat-PRP residue (A)     = 0x1D7AA56A5428333C,30698378043,40327643421
Processed 99 bits in binary modpow; MaxErr = 0.406250000
3^(F-1) residue (B)        = 0x6F856680482D3F4E, 9072042323,48656226334
(A - B) Res64 = 0xADF53EEA0BFAF3EE, C Res64 = 0xFFF9D50500000001
(A - B)/C: Quotient = 26538003597554197569639536298, Remainder Res64 = 0xEDFCE7FC50271D44
Suyama Cofactor-PRP test of F30 / 640126220763137 / 1095981164658689 with FFT length 62914560 = 61440 K:
(A - B) mod C has Res64,35m1,36m1: 0xEDFCE7FC50271D44, 9723857098,34401987830.
This cofactor is COMPOSITE [C323228467]. Checking prime-power-ness via GCD(A - B,C) ...
GCD((A - B)[1073741760 bits], C[1073741725 bits]) = 1
Time for GCD = 00:11:38.593
Cofactor is not a prime power.

 Similar Threads Thread Thread Starter Forum Replies Last Post ATH Operazione Doppi Mersennes 2 2015-01-25 06:27 Erasmus Math 46 2014-08-08 20:05 T.Rex Math 4 2005-05-07 08:25 T.Rex Math 2 2004-09-11 07:26 devarajkandadai Math 8 2004-07-27 12:27

All times are UTC. The time now is 09:41.

Tue Jun 28 09:42:00 UTC 2022 up 75 days, 7:43, 1 user, load averages: 0.97, 0.94, 0.94