In mathematics, the Lucas–Lehmer test (LLT) is a primality test for Mersenne numbers. The test was originally developed by Édouard Lucas in 1878 and subsequently proved by Derrick Henry Lehmer in 1930.
The test The Lucas–Lehmer test works as follows. Let Mp = 2p − 1 be the Mersenne number to test with p an odd prime. The primality of p can be efficiently checked with a simple algorithm like trial division since p is exponentially smaller than Mp. Define a sequence { s i } {\displaystyle \{s_{i}\}} for all i ≥ 0 by
s i = { 4 if i = 0 ; s i − 1 2 − 2 otherwise. {\displaystyle s_{i}={\begin{cases}4&{\text{if }}i=0;\\s_{i-1}^{2}-2&{\text{otherwise.}}\end{cases}}}
The first few terms of this sequence are 4, 14, 194, 37634, ... (sequence A003010 in the OEIS). Then Mp is prime if and only if
s p − 2 ≡ 0 ( mod M p ) . {\displaystyle s_{p-2}\equiv 0{\pmod {M_{p}}}.}
The number sp − 2 mod Mp is called the Lucas–Lehmer residue of p. (Some authors equivalently set s1 = 4 and test sp−1 mod Mp). In pseudocode, the test might be written as
// Determine if Mp = 2p − 1 is prime for p > 2 Lucas–Lehmer(p) var s = 4 var M = 2p − 1 repeat p − 2 times: s = ((s × s) − 2) mod M if s == 0 return PRIME else return COMPOSITE
Performing the mod M at each iteration ensures that all intermediate results are at most p bits (otherwise the number of bits would double each iteration). The same strategy is used in modular exponentiation.
Alternative starting values Starting values s0 other than 4 are possible, for instance 10, 52, and others (sequence A018844 in the OEIS). The Lucas–Lehmer residue calculated with these alternative starting values will still be zero if Mp is a Mersenne prime. However, the terms of the sequence will be different and a non-zero Lucas-Lehmer residue for non-prime Mp will have a different numerical value from the non-zero value calculated when s0 = 4. It is also possible to use the starting value (2 mod Mp)(3 mod Mp)−1, usually denoted by 2/3 for short. This starting value equals (2p + 1) /3, the Wagstaff number with exponent p. Starting values like 4, 10, and 2/3 are universal, that is, they are valid for all (or nearly all) p. There are infinitely many additional universal starting values. However, some other starting values are only valid for a subset of all possible p, for example s0 = 3 can be used if p = 3 (mod 4). This starting value was often used where suitable in the era of hand computation, including by Lucas in proving M127 prime. The first few terms of the sequence are 3, 7, 47, ... (sequence A001566 in the OEIS).
Sign of penultimate term If sp−2 = 0 mod Mp then the penultimate term is sp−3 = ± 2(p+1)/2 mod Mp. The sign of this penultimate term is called the Lehmer symbol ϵ(s0, p). In 2000 S.Y. Gebre-Egziabher proved that for the starting value 2/3 and for p ≠ 5 the sign is:
ϵ ( 2 3 , p ) = ( − 1 ) p − 1 2 {\displaystyle \epsilon ({2 \over 3},\ p)=(-1)^{p-1 \over 2}}
That is, ϵ(2/3, p) = +1 if p = 1 (mod 4) and p ≠ 5. The same author also proved Woltman's conjecture that the Lehmer symbols for starting values 4 and 10 when p is not 2 or 5 are related by:
ϵ ( 10 , p ) = ϵ ( 4 , p ) × ( − 1 ) ( p + 1 ) ( p + 3 ) 8 {\displaystyle \epsilon (10,\ p)=\epsilon (4,\ p)\ \times \ (-1)^{{(p+1)(p+3)} \over 8}}
That is, ϵ(4, p) × ϵ(10, p) = 1 if p = 5 or 7 (mod 8) and p ≠ 2, 5. OEIS sequence A123271 shows ϵ(4, p) for each Mersenne prime Mp.
Time complexity In the algorithm as written above, there are two expensive operations during each iteration: the multiplication s × s, and the mod M operation. The mod M operation can be made particularly efficient on standard binary computers by observing that
k ≡ ( k mod 2 n ) + ⌊ k / 2 n ⌋ ( mod 2 n − 1 ) . {\displaystyle k\equiv (k\,{\bmod {\,}}2^{n})+\lfloor k/2^{n}\rfloor {\pmod {2^{n}-1}}.}
… excerpt ends here. Continue reading the full article.
