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

151910 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

22×3×7×139 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

27578 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].

 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 21:52.

Mon Dec 6 21:52:07 UTC 2021 up 136 days, 16:21, 1 user, load averages: 2.26, 2.38, 2.85