Quote:
Originally Posted by ewmayer
@Jeppe: This is simply the basic Pépin residue ... (And also one wants the 2nd doublecheck run at the slightly larger FFT length to finish and confirm the Pépintest 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 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.