DOUBLE
CHECKING
To verify that a first-time Lucas-Lehmer primality
test was performed without error, GIMPS runs the primality test a second time.
During each test, the low order 64 bits of the final S (P)-2 value, called a residue,
are printed. If these match, then GIMPS declares the exponent properly
double-checked. If they do not match, then the primality test is run again
until a match finally occurs.
GIMPS goes a bit further to guard against programming
errors. Prior to starting the Lucas-Lehmer test, the S (0) value is left
shifted by a random amount. Each squaring just doubles how much we have shifted
the S value. Note that the mod 2P-1 step merely rotates the p-th
bits and above to the least significant bits, so there is no loss of
information. Why do we go to this trouble? If there were a bug in the FFT code,
then the shifting of the S values insures that the FFTs in the first primality
test are dealing with completely different data than the FFTs in the second
primality test. It would be near impossible for a programming bug to produce
the same final 64 bit residues.
Historically, the error rate for a Lucas-Lehmer test
is a little over one percent.