The test was originally developed by Édouard Lucas in 1878[1] and subsequently proved by Derrick Henry Lehmer in 1930.
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.
In pseudocode, the test might be written as 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).
Starting values s0 other than 4 are possible, for instance 10, 52, and others (sequence A018844 in the OEIS).
[2] 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.
[2] 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).
[3] This starting value was often used where suitable in the era of hand computation, including by Lucas in proving M127 prime.
The sign of this penultimate term is called the Lehmer symbol ϵ(s0, p).
Gebre-Egziabher proved that for the starting value 2/3 and for p ≠ 5 the sign is: That is, ϵ(2/3, p) = +1 if p = 1 (mod 4) and p ≠ 5.
[2] OEIS sequence A123271 shows ϵ(4, p) for each Mersenne prime Mp.
The mod M operation can be made particularly efficient on standard binary computers by observing that This says that the least significant n bits of k plus the remaining bits of k are equivalent to k modulo 2n−1.
In this way, the remainder after dividing k by the Mersenne number 2n−1 is computed without using division.
For example, Moreover, since s × s will never exceed M2 < 22p, this simple technique converges in at most 1 p-bit addition (and possibly a carry from the pth bit to the 1st bit), which can be done in linear time.
The simple "grade-school" algorithm for multiplication requires O(p2) bit-level or word-level operations to square a p-bit number.
By comparison, the most efficient randomized primality test for general integers, the Miller–Rabin primality test, requires O(k n2 log n log log n) bit operations using FFT multiplication for an n-digit number, where k is the number of iterations and is related to the error rate.
For constant k, this is in the same complexity class as the Lucas-Lehmer test, and is similarly fast in practice.
The most efficient deterministic primality test for any n-digit number, the AKS primality test, requires Õ(n6) bit operations in its best known variant and is extremely slow even for relatively small values.
Initially s is set to 4 and then is updated 3−2 = 1 time: Since the final value of s is 0, the conclusion is that M3 is prime.
Again, s is set to 4 but is now updated 11−2 = 9 times: Since the final value of s is not 0, the conclusion is that M11 = 2047 is not prime.
Recall the definition The goal is to show that Mp is prime iff
What follows is a straightforward proof exploiting elementary group theory given by J. W. Bruce[7] as related by Jason Wojciechowski.
[note 2] The subset of elements in X with inverses forms a group, which is denoted by X* and has size
By Euler's criterion, this is equivalent to In contrast, 2 is a quadratic residue modulo
This time, Euler's criterion gives Combining these two equivalence relations yields Let
The Lucas–Lehmer test was the main primality test used by the Great Internet Mersenne Prime Search (GIMPS) to locate large primes until 2021.
This search has been successful in locating many of the largest primes known to date.
The test is considered valuable because it can provably test a large set of very large numbers for primality within an affordable amount of time.
In contrast, the equivalently fast Pépin's test for any Fermat number can only be used on a much smaller set of very large numbers before reaching computational limits.