In mathematics, the Lucas–Lehmer test (LLT) is a primality test for Mersenne numbers. The test was originally developed by Édouard Lucas in 1856 and subsequently improved by Lucas in 1878 and Derrick Henry Lehmer in the 1930s.
Contents
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
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
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 > 2Lucas–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 COMPOSITEPerforming 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.
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
This says that the least significant n bits of k plus the remaining bits of k are equivalent to k modulo 2n−1. This equivalence can be used repeatedly until at most n bits remain. 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. This algorithm has a small exceptional case. It will produce 2n−1 for a multiple of the modulus rather than the correct value of 0. However, this case is easy to detect and correct.
With the modulus out of the way, the asymptotic complexity of the algorithm only depends on the multiplication algorithm used to square s at each step. The simple "grade-school" algorithm for multiplication requires O(p2) bit-level or word-level operations to square a p-bit number. Since this happens O(p) times, the total time complexity is O(p3). A more efficient multiplication algorithm is the Schönhage–Strassen algorithm, which is based on the Fast Fourier transform. It only requires O(p log p log log p) time to square a p-bit number. This reduces the complexity to O(p2 log p log log p) or Õ(p2). Currently the most efficient known multiplication algorithm, Fürer's algorithm, only needs
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. In practice however, the cost of doing many iterations and other differences leads to worse performance for Miller–Rabin. 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 dramatically slower in practice.
Examples
The Mersenne number M3 = 7 is prime. The Lucas–Lehmer test verifies this as follows. 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.
On the other hand, M11 = 2047 = 23 × 89 is not 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. Although M11 = 2047 has nontrivial factors, the Lucas–Lehmer test gives no indication about what they might be.
Proof of correctness
The proof of correctness for this test presented here is simpler than the original proof given by Lehmer. Recall the definition
The goal is to show that Mp is prime iff
The sequence
and
The last step uses
Sufficiency
The goal is to show that
Suppose
for some integer k, so
Multiplying by
Thus,
For a contradiction, suppose Mp is composite, and let q be the smallest prime factor of Mp. Mersenne numbers are odd, so q > 2. Informally, let
Clearly, this multiplication is closed, i.e. the product of numbers from X is itself in X. The size of X is denoted by
Since q > 2, it follows that
Now
in X. Then by equation (1),
in X, and squaring both sides gives
Thus
The order of an element is at most the order (size) of the group, so
But q is the smallest prime factor of the composite
This yields the contradiction
Necessity
In the other direction, the goal is to show that the primality of
Since
In contrast, 2 is a quadratic residue modulo
Combining these two equivalence relations yields
Let
where the first equality uses the Binomial Theorem in a finite field, which is
and the second equality uses Fermat's little theorem, which is
for any integer a. The value of
All that remains is to multiply both sides of this equation by
Since
Applications
The Lucas–Lehmer test is the primality test used by the Great Internet Mersenne Prime Search to locate large primes. 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.