View Single Post
Old 2020-01-25, 20:52   #78
R. Gerbicz
R. Gerbicz's Avatar
"Robert Gerbicz"
Oct 2005

112×13 Posts

Originally Posted by ewmayer View Post
@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
R. Gerbicz is offline   Reply With Quote