∂^{2}ω=0
Sep 2002
República de California
11,743 Posts

F25F30 cofactor status, Part 2
In each case I begin with a quick Pépintest residue sanity check, summarized here:
Quote:
For PRPtests of N with knownfactors (e.g. prelude to a cofactorPRP 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 veryvery strong
check, but the two known factors could find a mismatch with probability = 1(1e10) which is
still quite impressive. Note that we don't get the strength of 1/(q1) 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épintest 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^(q1) == 1 (mod q), thus
a^pow == a^pow' (mod q), where pow' = pow (mod q1).
Example: For the final Pépintest residue R for F30 (N = 2^2^30 + 1, pow = (N1)/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 p1) = 433448099512320, R == 367500396407933 (mod p)
q: pow' = 2^(2^30  1) (mod q1) = 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) squaringchain checksum computed as above.
For all the key quantities I give the "enhanced SelfridgeHurwitz residue" triplet, which consists of residues mod 2^64 (hex), 2^351 and 2^361, 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 Part1linked 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 reran @2048K FFT and confirmed the same values):
Computing 33554431squaring residue R (mod known prime q = 25991531462657)
A: R == 5785371429337 (mod q)
B: R == 5785371429337 (mod q)
Computing 33554431squaring residue R (mod known prime q = 204393464266227713)
A: R == 45685916416586703 (mod q)
B: R == 45685916416586703 (mod q)
Computing 33554431squaring residue R (mod known prime q = 2170072644496392193)
A: R == 991358595838356746 (mod q)
B: R == 991358595838356746 (mod q)
F25: using FFT length 1792K = 1835008 8byte floats.
this gives an average 18.285714285714285 bits per digit
Doing one modF25 squaring of iteration33554431 residue [Res64 = CB913B6E3B1FFE2A] to get FermatPRP residue
FermatPRP residue (A) = 0x7B6B087B84A45562,26994100025,66886679148
Processed 162 bits in binary modpow; MaxErr = 0.203125000
3^(F1) residue (B) = 0x2909830729BFA110,30348546187,21153567739
(A  B) Res64 = 0x526185745AE4B453, C Res64 = 0x21CC1C03F0000001
(A  B)/C: Quotient = 10040206794592865905247433568023540557761720874501, Remainder Res64 = 0x7A551893ACF4BE4E
Suyama CofactorPRP 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 primepowerness 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 reran @4096K FFT and confirmed the same values):
Computing 67108863squaring residue R (mod known prime q = 76861124116481)
A: R == 10772922302714 (mod q)
B: R == 10772922302714 (mod q)
F26: using FFT length 3584K = 3670016 8byte floats.
this gives an average 18.285714285714285 bits per digit
Doing one modF26 squaring of iteration67108863 residue [Res64 = 2B58BDE2A0C14045] to get FermatPRP residue
FermatPRP residue (A) = 0xFBB406B3A281838C, 2193939191, 7371940776
Processed 46 bits in binary modpow; MaxErr = 0.187500000
3^(F1) residue (B) = 0x25F5AB0FFC728C87,32173443562,20444894301
(A  B) Res64 = 0xD5BE5BA3A60EF705, C Res64 = 0x23FFBA1860000001
(A  B)/C: Quotient = 49561426973911, Remainder Res64 = 0xB7BD14979ACF222E
Suyama CofactorPRP 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 primepowerness 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 reran @7.5M and 8M FFT and confirmed the same values):
Computing 134217727squaring residue R (mod known prime q = 151413703311361)
A: R == 36549260191848 (mod q)
B: R == 36549260191848 (mod q)
Computing 134217727squaring residue R (mod known prime q = 231292694251438081)
A: R == 68921389296064753 (mod q)
B: R == 68921389296064753 (mod q)
F27: using FFT length 7168K = 7340032 8byte floats.
this gives an average 18.285714285714285 bits per digit
Doing one modF27 squaring of iteration134217727 residue [Res64 = 043A6C8B9272B297] to get FermatPRP residue
FermatPRP residue (A) = 0xC3B191C45CCD7820,21887650168,55240256170
Processed 104 bits in binary modpow; MaxErr = 0.281250000
3^(F1) residue (B) = 0x485F292142F953EC,20036545122,26481669619
(A  B) Res64 = 0x7B5268A319D42434, C Res64 = 0xD8C9BECF60000001
(A  B)/C: Quotient = 13668745121613830518711853822333, Remainder Res64 = 0x79E89190C56372B7
Suyama CofactorPRP 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 primepowerness 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 reran @16M FFT and confirmed the same values):
Computing 268435455squaring residue R (mod known prime q = 1766730974551267606529)
A: R == 688455961638747199546 (mod q)
B: R == 688455961638747199546 (mod q)
F28: using FFT length 15360K = 15728640 8byte floats.
this gives an average 17.066666666666666 bits per digit
Doing one modF28 squaring of iteration268435455 residue [Res64 = 468731C3E6F13E8F] to get FermatPRP residue
FermatPRP residue (A) = 0x7CAE1275B362B2CA,20461105324,30894284803
Processed 70 bits in binary modpow; MaxErr = 0.296875000
3^(F1) residue (B) = 0xBD496177DB5155A0,33633822046, 3778945069
(A  B) Res64 = 0xBF64B0FDD8115D2B, C Res64 = 0x39AEB33000000001
(A  B)/C: Quotient = 585290509330851034797, Remainder Res64 = 0x790BE051D73D667E
Suyama CofactorPRP 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 primepowerness 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 reran @32M FFT and confirmed the same values):
Computing 536870911squaring 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 FFTkblocks ... assuming a prev18 savefile.
F29: using FFT length 30720K = 31457280 8byte floats.
this gives an average 17.066666666666666 bits per digit
Doing one modF29 squaring of iteration536870911 residue [Res64 = BECE1E5FFBE5EC12] to get FermatPRP residue
FermatPRP residue (A) = 0x9BD416DB3918C152,32748692453,58920206666
Processed 51 bits in binary modpow; MaxErr = 0.375000000
3^(F1) residue (B) = 0x30AFC6010F62884B, 7473784009, 6544795868
(A  B) Res64 = 0x6B2450DA29B63908, C Res64 = 0x3FF7746780000001
(A  B)/C: Quotient = 1671099484324226, Remainder Res64 = 0xAB3DBCEFFE907786
Suyama CofactorPRP 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 primepowerness 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 reran @64M FFT and confirmed the same values):
Computing 1073741823squaring residue R (mod known prime q = 640126220763137)
A: R == 367500396407933 (mod q)
B: R == 367500396407933 (mod q)
Computing 1073741823squaring residue R (mod known prime q = 1095981164658689)
A: R == 95971534699540 (mod q)
B: R == 95971534699540 (mod q)
F30: using FFT length 61440K = 62914560 8byte floats.
this gives an average 17.066666666666666 bits per digit
Doing one modF30 squaring of iteration1073741823 residue [Res64 = A70C2A3DB98D6D9D] to get FermatPRP residue
FermatPRP residue (A) = 0x1D7AA56A5428333C,30698378043,40327643421
Processed 99 bits in binary modpow; MaxErr = 0.406250000
3^(F1) residue (B) = 0x6F856680482D3F4E, 9072042323,48656226334
(A  B) Res64 = 0xADF53EEA0BFAF3EE, C Res64 = 0xFFF9D50500000001
(A  B)/C: Quotient = 26538003597554197569639536298, Remainder Res64 = 0xEDFCE7FC50271D44
Suyama CofactorPRP 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 primepowerness 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.
