Lucas-Lehmer test

From Mersennewiki

(Redirected from Lucas-Lehmer Test)

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.

Contents

History

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.

Simple Explanation

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 S_{p-2} = 0 ( 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.

Advanced Explanation

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 m such that a^m\eq 1 (mod N), where a 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 p is a prime number greater than 2 and the Lucas sequence is defined by S_0=4 and S_{n+1}=S_n^2-2, then 2^p-1 is prime if and only if S_{p-2} is divisible by 2^p-1. 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 \omega =2+\sqrt 3 and \bar \omega =2-\sqrt 3 and then define L_n to be \omega^{2^{n}} + \bar\omega^{2^{n}}, we get L_0\,=\,\omega+\bar\omega\,=\,4 and (since \omega\bar\omega\,=\,1) L_{n+1}=\omega^{2^{n+1}} + \bar\omega^{2^{n+1}}\,=\,\omega^{2^{n+1}} + \bar\omega^{2^{n+1}} + 2\,\omega^{2^{n}}\,\bar\omega^{2^{n}}\, -\, 2\, =\,(\omega^{2^{n}} + \bar\omega^{2^{n}})^2\,-\,2\,=\, L_n^2-2. Because the L_n satisfy the same inductive definition as the Lucas sequence numbers S_n, the two sequences must be the same.

Proof of Necessity

 If p is an odd prime and 2^p-1 is prime then S_{p-2} is divisible by 2^p-1.

Rosen's proof is fairly elementary, but uses some basic facts about quadratic reciprocity. One such fact is that if a is relatively prime to an odd prime q, then a^{{q-1}\over 2} will be congruent to \pm 1 mod q depending on whether a is a quadratic residue (+1) or a quadratic non-residue (-1).

Let Q=2^p-1, and let's consider numbers of the form a+b\sqrt 3 \,\pmod Q. Now use the binomial theorem to expand (1+\sqrt 3)^Q\,\pmod Q. Because Q is prime, it will be a factor of all the binomial coefficients except the first and the last, so we get that (1+\sqrt 3)^Q\,\eq \,1+(\sqrt 3)^Q\,\pmod Q, which equals 1+(\sqrt 3)3^{{Q-1}\over 2}\,\pmod Q. Quadratic reciprocity says that 3^{{Q-1}\over 2} is congruent to \pm 1\,\pmod Q, and we can easily determine the correct sign: Since Q and 3 are both congruent to -1 mod 4, the law of quadratic reciprocity says that either Q is a quadratic residue mod 3 or 3 is a quadratic residue mod Q but not both. But Q=2^p-1 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 Q, implying that 3^{{Q-1}\over 2}\,\eq \,-1\,\pmod Q so (1+\sqrt 3)^Q\,\eq \,1-(\sqrt 3)\,\pmod Q. Multiplying both sides by 1+\sqrt 3, we get that (1+\sqrt 3)^{Q+1}\,\eq \,-2\,\pmod Q. Now use (1+\sqrt 3)^2\,= \,2\omega to write (2\omega)^{{Q+1}\over 2}\,\eq \,-2\,\pmod Q. The left-hand side of this equation is equal to 2^{{Q+1}\over 2}\omega^{{Q+1}\over 2}\,= \,2* 2^{{Q-1}\over 2}\omega^{{Q+1}\over 2}. Again, 2 is a quadratic residue of primes congruent to \pm 1 mod 8, and Q is of this form, so we get that 2^{{Q-1}\over 2}\,\eq \,1\,\pmod Q, which allows us to rewrite the above relation as 2\omega^{{Q+1}\over 2}\,\eq \,-2\,\pmod Q. 2 has an inverse mod Q, namely {Q+1}\over 2, so multiplying by the inverse will cancel the 2 giving us \omega^{{Q+1}\over 2}\,\eq \,-1\,\pmod Q. Write this as \omega^{2^{p-1}}\,\eq \,\omega^{2^{p-2}}\omega^{2^{p-2}}\,\eq \,-1\,\pmod Q, multiply both sides by \bar\omega^{2^{p-2}}, and put both terms on the left-hand side to write this as \omega^{2^{p-2}}+\bar\omega^{2^{p-2}}\,\eq \,0\,\pmod Q, or S_{p-2}\,\eq \,0\,\pmod Q. Since the left-hand side is an integer, this means therefore that S_{p-2} must be divisible by Q, i.e. by 2^p-1.

Proof of Sufficiency

 If S_{p-2} is divisible by 2^p-1, then 2^p-1 is prime.

The proof that the Lucas-Lehmer test proves the primality of 2^p-1 devised by Bruce is elegant in its simplicity, and it will be shown here with a couple of minor simplifications.

If 2^p-1 is not prime, then it must be divisible by some prime factor F less than or equal to the square root of 2^p-1. From the hypothesis S_{p-2} is divisible by 2^p-1, so S_{p-2} is also a multiple of F, so we can write \omega^{2^{p-2}} + \bar\omega^{2^{p-2}}=KF for some integer K. Note that \omega\bar\omega=1, so we can multiply both sides by \omega^{2^{p-2}} and rewrite this relation as \omega^{2^{p-1}}=KF\omega^{2^{p-2}}-1. If we square both sides, we get \omega^{2^{p}}=(KF\omega^{2^{p-2}}-1)^2. Now consider the set of "numbers" a+b\sqrt 3 for integers a and b where a+b\sqrt 3 and c+d\sqrt 3 are considered equivalent if a and c differ by a multiple of F, i.e., are equal "modF", and the same is true for b and d. There are F^2 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 a+b\sqrt 3 is equivalent to a'+b'\sqrt 3 and c+d\sqrt 3 is equivalent to c'+d'\sqrt 3, then (a+b\sqrt 3)(c+d\sqrt 3) is equivalent to (a'+b'\sqrt 3)(c'+d'\sqrt 3) and similarly for addition.) The number 1=1+0\sqrt 3 (or, more properly, the equivalence class of all numbers equivalent to 1 mod F) is a multiplicative identity element, but not all elements have a multiplicative inverse, for example, 0=0+0\sqrt 3 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 \omega (considered as a representative of an equivalence class), the associative law allows us to use the exponential notation for repeated products: \omega^n=\omega\omega...\omega where the product contains n factors, and the usual rules for exponents can then be justified. Consider the sequence of elements \omega,\omega^2,\omega^3,.... Because \omega has the inverse \bar\omega, every element in this sequence has an inverse and zero can never occur, so there can be at most F^2-1 different elements of this sequence. Thus there must be at least two different exponents where \omega^j=\omega^k with j<k\le F^2. Multiply j times by the inverse of \omega to get that \omega^{k-j}=1, with 1\le k-j\le F^2-1. We have proven that \omega satisfies \omega^n=1 for some positive exponent n less than or equal to F^2-1, (in general less than or equal to the number of elements in the group). Define the "order" of \omega to be the smallest positive integer d such that \omega^d=1. We claim that if n is any other positive integer satisfying \omega^n=1, then n must be a multiple of d. Write n=qd+r with r<d a non-negative remainder. Then if r\neq 0, we have 1=\omega^n=\omega^{qd+r}=(\omega^d)^q\omega^r=1^q\omega^r=\omega^r, contradicting the minimality of d, so r=0 and n is therefore a multiple of d. (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 \omega^{2^{p}}=(KF\omega^{2^{p-2}}-1)^2 shows that under our modF equivalence, \omega^{2^{p}}=1 so that 2^p must be a multiple of the order of \omega. But the relation \omega^{2^{p-1}}=KF\omega^{2^{p-2}}-1 then shows that \omega^{2^{p-1}}\,\eq \,-1\,\pmod F so the order can not be any proper factor of 2^p, therefore the order must be 2^p. Since this order is less than or equal to F^2-1 and F is less than or equal to the square root of 2^p-1, we get the contradiction that 2^p\le F^2-1\le 2^p-2. So therefore 2^p-1 must be prime.

LLT DiGraph

Let call a digraph G_{n,f(x)} a graph made of the pairs a \to b, where a belongs to the set 0, 1, 2 ..., n-1 and f(a) \equiv b \ \pmod{n}. When n is any number, its digraph is made of cycles, trees and/or tails. (Example: a cycle with f(x)=x^2 is: a \to a^2 \to a^{2^2} \to a^{2^3} \to ... \to 2^{2^x} \equiv a).

When M_q = 2^q-1 is a prime, the representation of the digraph G_{M_q,x \to x^2-2} 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 G_{M_q,x \to x^2-2} consists of: (i) A reversed complete binary tree of height q-1 with root 0, attached to the node -2, which is attached to the node 2 with a cycle of length 1 on this node. (ii) A set of cycles of length dividing q-1.

The roots of the tree are given by the suite: x_{i+1} = x_i(x_i^2-3) \ \bmod{M_q}, starting with: x_0 = 4.

Tony Reix guessed and "ZetaX" (AOPS forum) proved the formula that computes the number of cycles of a given length under x\to x^2-2 modulo a Mersenne prime M_q:

For each d such that d \ \mid \ n with n = q-1 = 2^s u where u is odd, the number of cycles of length d is:
\frac{1}{n} \left( \sum\limits_{d|n} \mu \left( \frac{n}{d} \right) 2^d - \sum\limits_{2^s|d|n} \mu \left( \frac{n}{d} \right) 2^{d-1} \right),
where \mu(x) is the well-known Moebius function.

As an example, the number of cycles of length 20 for q=521 is: 52377. The number of cycles of length 20 for q=61 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 I_k=\omega^k + \bar\omega^k, where k is positive odd integer, can be used as an initial value S_0 for LLT. For example, I_1=4 gives the standard initial value.

Initial values I_k modulo M_q have the period 2^q, i.e., I_k \equiv I_{k\bmod 2^q}\pmod{M_q}. There are 2^{q-2} distinct initial values modulo M_q 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 I_k \equiv I_{2^q - k}\pmod{M_q} for k<2^q.

All initial values can be also obtained as the union of two recurrent sequences: a_1=4,\ a_2=52,\ a_{n}=14 a_{n-1} - a_{n-2} and b_1=10,\ b_2=970,\ b_{n}=98 b_{n-1} - b_{n-2} giving rise to the sequence A018844 in OEIS.

Sequence c_0=4,\ c_{n}=c_{n-1}^3-3c_{n-1}\bmod M_q also generates all distinct initial values modulo M_q with n=0..2^{q-2}-1. In this case we have c_n=I_{3^n}\bmod M_q.

Universal Initial Values

2^{q-2} initial values can be used as S_0 for a given Mersenne number M_q=2^{q}-1 (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  \frac{2}{3} \,\eq \,\frac{2^{q}+1}{3}.

Notice that the original 3 LLTs can be modified in order to produce equivalent tests, like: (from 4) S_0=2 ,\  S_{i+1} = 2 S_i^2-1\ , or (from 10): S_0=5 ,\ S_{i+1}=2S_i^2-1\ , or: (from 2/3) S_0=2 , \ S_{i+1}=S_i^2/3 - 6\ , or many others, by induction.

Complexity

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)

Contributions

R. D. Silverman

cheesehead

Zeta-Flux

Phil Moore

Dougy

Numbers

T.Rex

smh

maxal

flouran

Personal tools