The Lucas-Lehmer test is a deterministic algorithm used to prove a Mersenne number either composite or prime. It is the last stage in the procedure employed by GIMPS for finding Mersenne Primes. Previous stages try to find factors, as explained on GIMPS factoring and sieving article.
The French mathematician Edouard Lucas (1842 - 91) developed an entirely new way of proving numbers prime without attempting to find all of their factors. Instead, he showed that if p = 1 (mod 4), and if 2p-1 is prime, then 2p-1 would divide into another number, now called a Lucas-Lehmer number denoted Sn where S0=4 and Sn = (Sn-1)2 − 2 . In 1930, the American mathematician Derrick Lehmer (1905 - 91) provided a complete proof that this was not only true when p = 1 (mod 4), but for all odd prime exponents. The test therefore takes its name from the two mathematicians who invented and developed it, even though they never met.
As described above, the test is not trying to find factors of the number being tested, but to determine whether or not it divides into a much bigger number. This bigger number, the Lucas-Lehmer number, is calculated as one in a sequence of numbers where each number is the previous number squared, minus 2. So that where S1 = 14, S2 = 142 - 2 = 194, and S3 = 1942 - 2 = 37634. So the fact that 25 - 1 divides S3 (37634 / 31 = 1214) shows that 25 - 1 is prime.
If you try to calculate a few more numbers in the Lucas-Lehmer sequence you will find that they get very much bigger very quickly. The value of S0 has about 2 (= 21) bits (a bit is the smallest unit of computer memory). The value of S1 has about 4 (= 22) bits, the value of S2 has about 8 (= 23) bits, and the value of S50000000 (which would need to be calculated in order to test any Mersenne number with an exponent larger than 50,000,000) has roughly 250000000 bits. That is, S50000000 is a number so big that its number of bits is the 50 millionth power of 2.
In order to appreciate the size of that number, let's consider the following: The number of particles (electrons, protons, neutrons, muons, etc.) in the known universe is less than 10100, according to recent estimates. 10100 is less than 2400. So if we could use every particle in the known universe to store one binary bit of information, the largest number whose binary (or decimal) expansion we could store would be less than 22400, which is much, much, much smaller than S50000000.
The computer sitting on your desk does not contain enough memory to hold the binary expansion of any of these numbers past the first few smallest terms. How is the calculation done if we cannot even hold the binary expansions on a computer?
The answer is modular arithmetic. In its simplest form, if we divide 7 into 12, the answer is that it goes 1, with a remainder of 5. We write this 12 = 5(mod 7). Similarly, we can write that 24 = 3 (mod 7), and 36 = 1 (mod 7).
We extend this to our Lucas-Lehmer test by taking the calculation of the Lucas-Lehmer number for 2p-1 (mod 2p-1). So that S3, instead of being 37634 becomes 0 (mod 31), for p=5. Now, if we were trying to calculate the Lucas-Lehmer number for 211-1, when we get to S3 this would now need to be calculated (mod 211-1) not (mod 25-1), and so S3 now becomes 788 (mod 2047).
This means that the modular remainders need to be calculated separately for each exponent that is being tested, and it is this set of calculations that forms the Lucas-Lehmer test. At the end of the test, if the final answer is that ( mod 2p-1 ), then 2p-1 is prime.
One consequence of the way the test works is that the test needs to go all the way to the end before any useful information comes out, because up to that point all that is happening is that the program is calculating the sequence of Lucas-Lehmer numbers.
With N=2p-1, we know all of the prime factors of N+1. There is a very old and simple way to prove N a prime if we know all of the factors of N-1: exhibit a primitive root. This works via Lagrange's Theorem. The order of an element of Z/NZ* (the smallest value such that (mod ), where is the element) must divide N-1. Now exhibit an element whose order is N-1 and we are done. To prove that an element has order N-1 we must show that it does not have order (N-1)/q for all primes q dividing N-1. Thus, if we know all the factors of N-1, we can prove N prime. Now consider the finite field F(N2). It has N2 elements and its unit *group*, GF(N2), has N2-1 elements. It also has a sub-group (known as the twisted group) whose order is N+1. The Lucas-Lehmer test does for N+1 what exhibiting a primitive root of N does in the N-1 case. It demonstrates that there is an element of the twisted group having full (i.e. maximal possible) order. Whereas for N-1, we do ordinary modular multiplication/ exponentiation to compute a^( (N-1)/q) mod N, in the twisted group the recursion Sn = Sn-12 - 2 effects the squaring and certain operations with Lucas sequences to perform the multiplication (but fortunately they are used only in the proof and not in the test because N+1 = 2p). We know N is prime when there is an element of full order. Note that the Lucas-Lehmer test can also be applied (with modifications to the recursion) to any suspected odd prime N when all the prime factors of N-1 or N+1 are known. (See Chapter 4.3 and 8.4 of Williams' book). When we test N = 2p-1, the recursion is particularly simple because all of the prime factors of N+1 are '2'. For the same reason, this test also applies to Fermat numbers 22n+1, as shown by Lucas (Theorem 5.2.2 of William's book).
Proof of the Lucas-Lehmer test
Lehmer's theorem says that if is a prime number greater than 2 and the Lucas sequence is defined by and , then is prime if and only if is divisible by . We offer here a relatively non-technical proof of this theorem based on the papers by M. I. Rosen and J. W. Bruce listed in the reference section below. As indicated in the previous section, a deeper understanding of the theorem requires a study of Lucas sequences, but this proof has the advantage that it can be understood by someone with a relatively limited knowledge of number theory.
If we define and and then define to be , we get and (since ) . Because the satisfy the same inductive definition as the Lucas sequence numbers , the two sequences must be the same.
Proof of Necessity
If is an odd prime and is prime then is divisible by .
Rosen's proof is fairly elementary, but uses some basic facts about quadratic reciprocity. One such fact is that if is relatively prime to an odd prime , then will be congruent to mod depending on whether is a quadratic residue () or a quadratic non-residue ().
Let , and let's consider numbers of the form . Now use the binomial theorem to expand . Because is prime, it will be a factor of all the binomial coefficients except the first and the last, so we get that , which equals . Quadratic reciprocity says that is congruent to , and we can easily determine the correct sign: Since and 3 are both congruent to -1 mod 4, the law of quadratic reciprocity says that either is a quadratic residue mod 3 or 3 is a quadratic residue mod but not both. But is easily verified to be congruent to 1 mod 3 and therefore is a quadratic residue mod 3, therefore 3 is not a quadratic residue mod , implying that so . Multiplying both sides by , we get that . Now use to write . The left-hand side of this equation is equal to . Again, 2 is a quadratic residue of primes congruent to mod 8, and is of this form, so we get that , which allows us to rewrite the above relation as . 2 has an inverse mod , namely , so multiplying by the inverse will cancel the 2 giving us . Write this as , multiply both sides by , and put both terms on the left-hand side to write this as , or . Since the left-hand side is an integer, this means therefore that must be divisible by , i.e. by .
Proof of Sufficiency
If is divisible by , then is prime.
The proof that the Lucas-Lehmer test proves the primality of devised by Bruce is elegant in its simplicity, and it will be shown here with a couple of minor simplifications.
If is not prime, then it must be divisible by some prime factor less than or equal to the square root of . From the hypothesis is divisible by , so is also a multiple of , so we can write for some integer . Note that , so we can multiply both sides by and rewrite this relation as . If we square both sides, we get . Now consider the set of "numbers" for integers and where and are considered equivalent if and differ by a multiple of , i.e., are equal "mod", and the same is true for and . There are of these numbers, and addition and multiplication can be verified to be well-defined on sets of equivalent numbers. (Exercise: prove this! One needs to show that if is equivalent to and is equivalent to , then is equivalent to and similarly for addition.) The number (or, more properly, the equivalence class of all numbers equivalent to 1 mod ) is a multiplicative identity element, but not all elements have a multiplicative inverse, for example, does not. In Bruce's proof, he considers the group consisting of all invertible elements under multiplication, but in fact, we do not need the full group structure, only the fact that multiplication is associative. Given the element (considered as a representative of an equivalence class), the associative law allows us to use the exponential notation for repeated products: where the product contains factors, and the usual rules for exponents can then be justified. Consider the sequence of elements . Because has the inverse , every element in this sequence has an inverse and zero can never occur, so there can be at most different elements of this sequence. Thus there must be at least two different exponents where with . Multiply times by the inverse of to get that , with . We have proven that satisfies for some positive exponent less than or equal to , (in general less than or equal to the number of elements in the group). Define the "order" of to be the smallest positive integer such that . We claim that if is any other positive integer satisfying , then must be a multiple of . Write with a non-negative remainder. Then if , we have , contradicting the minimality of , so and is therefore a multiple of . (Note that here we are using the laws of exponents justified by the associative law. In general, these are standard arguments which apply to any element of any group.) The relation shows that under our mod equivalence, so that must be a multiple of the order of . But the relation then shows that so the order can not be any proper factor of , therefore the order must be . Since this order is less than or equal to and is less than or equal to the square root of , we get the contradiction that . So therefore must be prime.
Let call a digraph a graph made of the pairs , where belongs to the set and . When is any number, its digraph is made of cycles, trees and/or tails. (Example: a cycle with is: ).
When is a prime, the representation of the digraph is completely known. This has been proved by Shallit and Vasiga in "On the iteration of certain quadratic maps over GF(p)".
Theorem 17 says: For Mersenne primes, the digraph consists of: (i) A reversed complete binary tree of height with root 0, attached to the node , which is attached to the node 2 with a cycle of length 1 on this node. (ii) A set of cycles of length dividing .
The roots of the tree are given by the suite: , starting with: .
Tony Reix guessed and "ZetaX" (AOPS forum) proved the formula that computes the number of cycles of a given length under modulo a Mersenne prime :
- For each d such that with where is odd, the number of cycles of length d is:
- where is the well-known Moebius function.
As an example, the number of cycles of length 20 for is: 52377. The number of cycles of length 20 for is: 26163.
This problem appeared in D. Shanks' book "Solved and Unsolved problems in Number Theory", Chapter ”Supplementary Comments, Theorems, and Exercises”, page 215 (Edition 1962).
Initial Values of LLT
Any number of the form , where is positive odd integer, can be used as an initial value for LLT. For example, gives the standard initial value.
Initial values modulo have the period , i.e., . There are distinct initial values modulo that may be obtained from the first (or second) half of the period. The other half repeats the same values in the reversed order, since for .
All initial values can be also obtained as the union of two recurrent sequences: and giving rise to the sequence A018844 in OEIS.
Sequence also generates all distinct initial values modulo with . In this case we have .
Universal Initial Values
initial values can be used as for a given Mersenne number (see previous section).
Samuel Gebre-Egziabher has shown that there are only 3 Universal Initial Values than can be used for all Mersenne numbers: 4, 10 and .
Notice that the original 3 LLTs can be modified in order to produce equivalent tests, like: (from 4) , or (from 10): , or: (from 2/3) , or many others, by induction.
The Lucas-Lehmer test, when used with the Fast Fourier transform, has a complexity of O(log2 N log log N) where N represents the Mersenne number. The complexity can also be represented as O(n2 log n) where n is the exponent of the Mersenne number.
Further Reading and References
D. H. Lehmer - An Extended Theory of Lucas' Functions, Annals of Mathematics, 31 (1930) 419-448.
M. I. Rosen - A Proof of the Lucas-Lehmer Test, The American Mathematical Monthly 64 (1988) no. 9, 855-856.
J. W. Bruce - A Really Trivial Proof of the Lucas-Lehmer Test, The American Mathematical Monthly 100 (1993) no. 4, 370-371.
G. H. Hardy, E. M. Wright - An Introduction to the Theory of Numbers, Oxford University Press, 1979
P. Ribenboim - The Little Book of Bigger Primes, Springer-Verlag 2004
R. Thompson - Thesis presented to the Reed College, 2002
Hugh C. Williams - Edouard Lucas and Primality Testing, Canadian Mathematical Society, 22 (1998)
R. D. Silverman