Node:Lucas-Lehmer test, Previous:Mersenne number, Up:Glucas internals
The Lucas-Lehmer test is a test of primality for Mersenne numbers (See Mersenne number.). This test was discovered by Lucas in 1870, and written in the definitive form by Lehmer in 1930. You can see more details about Lucas sequences here and about Lucas-Lehmer test in this page.
In short, the nicest thing of the Lucas-Lehmer test is its simplicity and
power. The recurrence sequence is as follows:
L(0) = 4 L(i+1) = ((L(i)*L(i) - 2) Mod M(p)here
A mod Bis the remainder of the integer division A/B.
And it is proven that M(p) is prime if and only if L(p-2) = 0
Thus, to see whether a Mersenne number M(p) is prime is very easy.
With the -D and -d command line options, it uses an initial
shift displacement of L(0) so the subsequent residues are related with the
unshifted original sequence by shifting (rotating) the proper amount of bits.
This allows Glucas to double-check L-L tests already tested with the
same program. DWT scrambles the data in such a way that two different initial
shifted sequences can be considered as independent.