20200125, 20:52  #78  
"Robert Gerbicz"
Oct 2005
Hungary
620_{16} Posts 
Quote:
(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 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. Last fiddled with by R. Gerbicz on 20200125 at 20:54 Reason: small typo 

20200127, 21:41  #79  
∂^{2}ω=0
Sep 2002
República de California
2DCF_{16} Posts 
Quote:
R == 367500396407933 (mod p) and R == 95971534699540 (mod q). I then separately computed 3^(2^(2^m  1)) mod p and q via (2^m1) = 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 64MFFT run update from Ryan), and said runs being done on highend server ssytems with ECC memory. For F31 I will also be using the nowfamous periodic wholeresidue check named in honor of the abovequoted forum member. :) Last fiddled with by ewmayer on 20200127 at 21:43 

20200128, 08:49  #80 
"Robert Gerbicz"
Oct 2005
Hungary
2^{5}·7^{2} Posts 
Trivial note: it is faster to reduce the exponent mod (p1) [use Fermat's little theorem].

20210702, 18:57  #81 
∂^{2}ω=0
Sep 2002
República de California
26717_{8} Posts 
Fermatmodmul with circularly shifted residues
I spent an appreciable amount of time last year wrestling with basic concepts and implementationincode of Fermatmod squaring chains in the presence of residue shift. This proves rather more interesting (a polite euphemism for "pain in the butt") than for the Mersennemod case. The Gerbicz check renders it less important, but it may still prove useful in some contexts, so figured I'd post a summary.
Let s0 = initial shift, i.e. instead of starting the Pépin test of Fm with initial seed x0, we start with (x0 << s0) (mod Fm). [1] Data layout: for Mersennemod IBDWT, we have 2 different wordsizes differing by one bit, so need to loop over the elements in our variablewordsize array until we find the one containing the (s0)th bit, then shift x0 by the appropriate small number of bits to place it on the proper bit boundary within that target word. For Fermatmod, the easy case is that of powerof2 FFT length, for which we have a fixed powerof2 wordsize. More generally we will have a nonpowerof2 FFT length optimized for the target modulus  e.g. for F24 we can use 896 Kdoubles, and for F30 I did one run at 60M and the other (now 93% complete) at 64M. In both cases we use a special acyclictransformeffecting DWT which multiplies our N input words by the first N (2N)th complex roots of unity, i.e. the (j)th input gets multiplied by DWT weight w[j] = exp(I*Pi*j/N). This means multiplying our original real input word by a complex number, but we notice that w[j+N/2] = I*w[j], making it natural to group the (j)th and (j+N/2)th input words together in memory and treat them as a single input to a complex FFT. This is the socalled "rightangle transform" trick, and is detailed in the original Crandall/Fagin 1994 DWT paper. In the Mersennemod IBDWT case we can also treat adjacent even/oddindexed imput elements as a single input to a complex FFT, but as the Mersennemod IBDWT weights are strictly real, these are simply pairs of adjacent input words. For Fermatmod arithmetic using a nonpowerof2length transform we need to layer a Mersennestyle dualwordlength base representation and similarly defined IBDWT weights atop our acycliceffecting DWT. One simplification relative to the Mersenne case is that for FFT length [odd]*2^k, the Fermatmod wordsizes and IBDWT weights recur in repeating length[odd] patterns. In the context of a rightangle Fermatmod acyclic transform, finding the target word for a given initialseed shift means looping first over the evenindexed elements of our residue vector (considered here as a lengthN real array), then if the accumulated wordsizes are still less than the target shift s0, looping over the oddindexed elements until we reach the target word. For the Fermatmod case we need only do this for the initial seed of the Pépin test; for the Mersennemod case, specifically the LucasLehmer test, we must also repeat the exercise on each subsequent iteration in order to find the proper bit offset for injection of the 2 term added to the outout of each modsquaring output. This can be done very efficiently  specifically in O(1) time  by initializing a suitable bitmap encoding the variable wordsizes of the Mersennemod IBDWT and using that to effect a fast lookup scheme. [2] For a basic squaringchainwithshift scheme as we do for Mersenne number M(p), each modsquaring doubles the shift count (mod p). That means that for any s0 != 0 (mod p) the shift will remain nonzero and nonrepeating during the LL/PRPtest, since at squaring i, our shift s = s0.2^i (mod p) and the multiplicative group (mod p) is of maximal order p1. OTOH for squaring chains modulo a Fermat number Fm, each subsequent squaring doubles the shift count (mod 2^m), so we have the problem that any nonzero initial shift s0 will lead to a shift s = 0 after precisely m squaremods, and the shift will remain 0 throughout the remainder of the squaring chain. One way to get around this problem is to define an auxiliary pseudorandombit array, and on the (i)th squaremod, if bit[i] = 1, do a further moddoubling of the residue, thus yielding the shiftcount update s[i] = 2.s[i1] + bit[i]. For a pair of Pépin tests of Fm such as are typically done to allow for realtime crossvalidation of interim residues, it is also advisable to seed the bitarrays differently for each run. [3] For the randombitoffset scheme in [2], we further need a postprocessing step to determine the correct sign to apply to the final residue; this relates to the shiftdoubling modulo the binary exponent which occurs on each squaremod. For Mp, squaring a shifted residue R.2^s gives R^2.2^2s (mod Mp) and 2^2s == 2^(2sp) (mod Mp), so at each iteration we simply double the shift count (mod p). For arithmetic modulo Fm, by way of contrast, each time the doubled shift count incurs a reduction (mod 2^m) the shifted residue undergoes a change of sign: R^2.2^2s (mod Fm) == R^2.2^(2s2^m) (mod Fm), so a shiftedresidue scheme must keep track of both the shift count and the sign of the shifted residue, relative to the true unshifted one. However: since  unlike LL  this PRP test involves just repeated modsquaring, we don't care if the sign of the residue on any particular intermediate iteration is flipped, since the subsequent modsquaring will flip it back to +. The only thing we care about is whether the sign of the final residue (either for the Pépin test or for a particular checkpoint subinterval thereof) has flipped w.r.to that of its immediate predecessor, the penultimate residue, since such a finalsquaring signflip has no ensuing modsquaring to autocorrect it. Thus, if there is a finalsquaring sign flip we need to unflip the sign of the resulting residue manually. But that is not all, since generating a shiftremoved final residue also involves a modular multiply or divide by a power of 2. I've always found it conceptually easier to multiplymod rather to dividemod, so for both that and lesscodetomaintain reasons, my mi64 multiword int library has lowlevel code only for leftward circular shift, and effects sbit rightward circular shift of a bbit number by a (bs)bit leftward one. That is all that is needed working modulo a Mersenne number, as these are of form 2^p1 and thus any bits offshifted to the left get rewrapped from the right with + sign. Once again, Fermat moduli are trickier. Modulo Fm, a leftward circular shift must feed the bits offshifted to the left back into the right end with a  sign, and the aforementioned shrcdoneasshlc substitution implies a negation (mod Fm) of the resulting shiftremoved residue. Thus, if at end of our current checkpoint interval or Pépin test, our residue R needed a signflip due the doubledshiftcount needing a reduction (mod 2^m), our shrcdoneasshlc already took care of it. If not, the residue needs an explicit negation. Rather than doing an explicit Fm  R with the attendant digitwise negations and borrows, one can simply do a bitwisecomplement of the residue vector and further += 2 of limb 0 in order to recover the unshifted residue. Last fiddled with by ewmayer on 20210804 at 00:42 Reason: ficks speelink 
20220513, 21:54  #82  
∂^{2}ω=0
Sep 2002
República de California
2DCF_{16} Posts 
F25F30 cofactor status, Part 1
[I PMed a moreorlessidentical draft of this to Prime95, ATH; yorix, jasonp, philmoore and R. Gerbicz yesterday]
F25F30 cofactor status: In the context of testing the cofactorPRP functionality which will be supported in Mlucas v21, I've at long last done Suyamastyle PRP tests on the cofactors of F25F30, using the Pépintest residues I've generated for same over the past 10 years, as detailed in this thread  original primalitytests for F2526 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 interimresidue files and logfile for the completed run @60 M FFT have been uploaded but the 99.5%complete doublecheck 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 cofactorPRP results are tabulated in a "Part 2" followup to this note. My code only supports the Suyama cofactorPRP method, which starts from the basic Pépintest residue, does one modsquaring to generate the FermatPRP residue A from that and an additional lg2(F) modsquarings 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 redo a similar amount of work when a new factor is discovered. I first added some basic cofactorPRP code to Mlucas in early 2018, and used it to test the cofactors of F2529 using the Pépintest residues I had generated via my primaiity tests for same. Did not post the cofactorPRP results at the time because the accompanying Res64 values mismatched ones posted by Andreas Höglund (a.k.a. ATH), who had done cofactorPRP 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 codeatthetime (2009) which Andreas used in fact was doing a directPRPtest of the cofactor, but I was unaware of the cofactorPRP runs for F25 and F26 done by forumite Yar (a.k.a. yorix  details below) in late 2017 using the thenlatest 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, PRPCF and PRPcert support, so in the context of the first, 'later' is now. In 20092010 Andreas Höglund used George's code to test the cofactors of F2527; cf. Posts #51, #62, #64 in this thread: Quote:
In late 2017 user Yar (don't know last name, uid = yorix) posted a thread about his own cofactorPRP runs for F2526, again using George's code, but now mentioning 2 different run types for each, which clarifies the types of cofactorPRP tests used: Quote:
For F25 and F26 my FermatPRP Res64 values match Yar's for the Suyamastyle cofactor check, and his directcofactor results match ATH's (though that is a samesoftwareused match). But it would be nice if someone using George's code could confirm not just the FermatPRP residues (A) for the above, but for purposes of pronouncing the ensuing cofactorPRP results "crossverified using independent codes", we should also crosscheck the (A  B) mod C ones, where C is the cofactor. The FermatPRP computation of course constitutes the overwhelming bulk of a PRPCF run, but it is important to also have assurance that the Bresidue 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 FermatPRPtest 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 crosscheck the (A  B) mod C residues. If not, the F25 and F26 fulllength tests are now easily runnable on modest hardware. Also, is there a different Prime95/mprime worktodoentry syntax for a directPRP test of a cofactor vs a 2step approach (FermatPRP 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 2step 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 Suyamastyle cofactorPRP 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 2030% more than a current GIMPS wavefrontPRP test. Results for my Mlucas v21prototype cofactorPRP runs follow in Part 2. 

20220513, 22:05  #83  
∂^{2}ω=0
Sep 2002
República de California
3^{2}·1,303 Posts 
F25F30 cofactor status, Part 2
In each case I begin with a quick Pépintest residue sanity check, summarized here:
Quote:
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. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
P1/P+1 on Fermat numbers  ATH  Operazione Doppi Mersennes  2  20150125 06:27 
What are the Primality Tests ( not factoring! ) for Fermat Numbers?  Erasmus  Math  46  20140808 20:05 
LLT numbers, linkd with Mersenne and Fermat numbers  T.Rex  Math  4  20050507 08:25 
Two Primality tests for Fermat numbers  T.Rex  Math  2  20040911 07:26 
Fermat Numbers  devarajkandadai  Math  8  20040727 12:27 