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

Sep 2002
República de California

2DDB16 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.