In mathematics, the Lucas–Lehmer test is a primality test for Mersenne numbers. The test was originally developed by Edouard Lucas in 1856 [1][2], and subsequently improved by Lucas in 1878 and Derrick Henry Lehmer in the 1930s.
Contents 
The LucasLehmer test works as follows. Let M_{p} = 2^{p} − 1 be the Mersenne number to test with p an odd prime (because p is exponentially smaller than M_{p}, we can use a simple algorithm like trial division for establishing its primality). Define a sequence {s_{ i}} for all i ≥ 0 by
The first few terms of this sequence are 4, 14, 194, 37634, ... (sequence A003010 in OEIS). Then M_{p} is prime iff
The number s_{p − 2} mod M_{ p} is called the Lucas–Lehmer residue of p. (Some authors equivalently set s_{1} = 4 and test s_{p−1} mod M_{p}). In pseudocode, the test might be written:
// Determine if M_{p} = 2^{p} − 1 is prime LucasLehmer(p) var s ← 4 var M ← 2^{p} − 1 repeat p − 2 times: s ← ((s × s) − 2) mod M if s = 0 return PRIME else return COMPOSITE
By performing the mod M
at each iteration, we
ensure that all intermediate results are at most p bits
(otherwise the number of bits would double each iteration). It is
exactly the same strategy employed in modular exponentiation.
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 the following simple
property:
In other words, if we take the least significant n bits of k, and add the remaining bits of k, and then do this repeatedly until at most n bits remain, we can compute the remainder after dividing k by the Mersenne number 2^{n}−1 without using division. For example:
916 mod 2^{5}−1  =  1110010100_{2} mod 2^{5}−1 
=  11100_{2} + 10100_{2} mod 2^{5}−1  
=  110000_{2} mod 2^{5}−1  
=  1_{2} + 10000_{2} mod 2^{5}−1  
=  10001_{2} mod 2^{5}−1  
=  10001_{2}  
=  17. 
Moreover, since s × s
will never exceed
M^{2} < 2^{2p}, this simple technique converges
in at most 2 pbit additions, which can be done in linear
time. As a small exceptional case, the above algorithm may produce
2^{n}−1 for a multiple of the modulus, rather than
the correct value of zero; this should be accounted for.
With the modulus out of the way, the asymptotic complexity of the algorithm depends only on the multiplication algorithm used to square s at each step. The simple "gradeschool" algorithm for multiplication requires O(p^{2}) bitlevel or wordlevel operations to square a pbit number, and since we do this O(p) times, the total time complexity is O(p^{3}). The most efficient known multiplication method, the SchönhageStrassen algorithm based on the Fast Fourier transform, requires O(p log p log log p) time to square a pbit number, reducing the complexity to O(p^{2} log p log log p) or Õ(p^{2}).^{[1]}
By comparison, the most efficient randomized primality test for general integers, the MillerRabin primality test, takes O(k p^{2} log p log log p) bit operations using FFT multiplication, where k is the number of iterations and is related to the error rate. This is a constant factor difference for constant k, but in practice the cost of doing many iterations and other differences lead to worse performance for MillerRabin. The most efficient deterministic primality test for general integers, the AKS primality test, requires Õ(p^{6}) bit operations in its best known variant and is dramatically slower in practice.
Suppose we wish to verify that M_{3} = 7 is prime using the LucasLehmer test. We start out with s set to 4 and then update it 3−2 = 1 time, taking the results mod 7:
Because we end with s set to zero, M_{3} is prime.
On the other hand, M_{11} = 2047 = 23 × 89 is not prime. To show this, we start with s set to 4 and update it 11−2 = 9 times, taking the results mod 2047:
Because s is not zero, M_{11}=2047 is not prime. Notice that we learn nothing about the factors of 2047, only its Lucas–Lehmer residue, 1736.
Lehmer's original proof of the correctness of this test is complex, so we'll depend upon more recent refinements. Recall the definition:
Then our theorem is that M_{p} is prime iff
We begin by noting that is a recurrence relation with a closedform solution. Define and ; then we can verify by induction that for all i:
where the last step follows from . We will use this in both parts.
In this direction we wish to show that implies that M_{p} is prime. We relate a straightforward proof exploiting elementary group theory given by J. W. Bruce^{[2]} as related by Jason Wojciechowski^{[3]}.
Suppose . Then for some integer k, and:
Now suppose M_{p} is composite with nontrivial prime factor q > 2 (all Mersenne numbers are odd). Define the set with q^{2} elements, where is the integers mod q, a finite field. The multiplication operation in X is defined by:
Since q > 2, ω and are in X. Any product of two numbers in X is in X, but it's not a group under multiplication because not every element x has an inverse y such that xy = 1. If we consider only the elements that have inverses, we get a group X* of size at most q^{2} − 1 (since 0 has no inverse).
Now, since , and , we have in X, which by equation (1) gives . Squaring both sides gives , showing that ω is invertible with inverse and so lies in X*, and moreover has an order dividing 2^{p}. In fact the order must equal 2^{p}, since and so the order does not divide 2^{p − 1}. Since the order of an element is at most the order (size) of the group, we conclude that . But since q is a nontrivial prime factor of M_{p}, we must have , yielding the contradiction 2^{p} < 2^{p} − 1. So M_{p} is prime.
In the other direction, we suppose M_{p} is prime and show . We rely on a simplification of a proof by Öystein J. R. Ödseth.^{[4]} First, notice that 3 is a quadratic nonresidue mod M_{p}, since 2^{ p} − 1 for odd p > 1 only takes on the value 7 mod 12, and so the Legendre symbol properties tell us (3  M_{p}) is −1. Euler's criterion then gives us:
On the other hand, 2 is a quadratic residue mod M_{p}, since and so . Euler's criterion again gives:
Next, define , and define X* similarly as before as the multiplicative group of . We will use the following lemmas:
(from Proofs of Fermat's little theorem#Proof_using_the_binomial_theorem)
for every integer a (Fermat's little theorem)
Then, in the group X* we have:
We chose σ such that ω = (6 + σ)^{2} / 24. Consequently, we can use this to compute in the group X*:
where we use the fact that
Since , all that remains is to multiply both sides of this equation by and use :
Since s_{p−2} is an integer and is zero in X*, it is also zero mod M_{p}.
The LucasLehmer test is the primality test used by the Great Internet Mersenne Prime Search to locate large primes, and has been successful in locating many of the largest primes known to date.^{[5]} They consider it valuable for finding very large primes because Mersenne numbers are considered somewhat more likely to be prime than randomly chosen odd integers of the same size. Additionally, the test is considered valuable because it can provably test a very large number for primality within affordable time and (in contrast to the equivalently fast Pépin's test for any Fermat number) can be tried on a large search space of numbers with the required form before reaching computational limits.

