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.

History

The French mathematician Édouard 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 2^p-1 is prime, then 2^p-1 would divide into another number, now called a Lucas-Lehmer number denoted S_n where S₀=4 and S_n = (S_n-1)² − 2. In 1930, the American mathematician Derrick Henry Lehmer (1905 - 1991) 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 S₁ = 14, S₂ = 14² - 2 = 194, and S₃ = 194² - 2 = 37634. So the fact that 2⁵ - 1 divides S₃ (37634 / 31 = 1214) shows that 2⁵ - 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 S₀ has about 2 (= 2¹) bits (a bit is the smallest unit of computer memory). The value of S₁ has about 4 (= 2²) bits, the value of S₂ has about 8 (= 2³) bits, and the value of S_50000000 (which would need to be calculated in order to test any Mersenne number with an exponent larger than 50,000,000) has roughly 2^50000000 bits. That is, S_50000000 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 10¹⁰⁰, according to recent estimates. 10¹⁰⁰ is less than 2⁴⁰⁰. 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 2²⁴⁰⁰, which is much, much, much smaller than S_50000000.

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 2^p-1 (mod 2^p-1). So that S₃, instead of being 37634 becomes 0 (mod 31), for p=5. Now, if we were trying to calculate the Lucas-Lehmer number for 2¹¹-1, when we get to S₃ this would now need to be calculated (mod 2¹¹-1) not (mod 2⁵-1), and so S₃ 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 [math]\displaystyle{ S_{p-2} = 0 }[/math] ( mod 2^p-1 ), then 2^p-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=2^p-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 [math]\displaystyle{ m }[/math] such that [math]\displaystyle{ a^m = 1 }[/math] (mod [math]\displaystyle{ N }[/math]), where [math]\displaystyle{ a }[/math] 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(N²). It has N² elements and its unit *group*, GF(N²), has N²-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 S_n = S_n-1² - 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 = 2^p). 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 = 2^p-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 2²ⁿ+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 [math]\displaystyle{ p }[/math] is a prime number greater than 2 and the Lucas sequence is defined by [math]\displaystyle{ S_0=4 }[/math] and [math]\displaystyle{ S_{n+1}=S_n^2-2 }[/math], then [math]\displaystyle{ 2^p-1 }[/math] is prime if and only if [math]\displaystyle{ S_{p-2} }[/math] is divisible by [math]\displaystyle{ 2^p-1 }[/math]. 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 [math]\displaystyle{ \omega =2+\sqrt 3 }[/math] and [math]\displaystyle{ \bar \omega =2-\sqrt 3 }[/math] and then define [math]\displaystyle{ L_n }[/math] to be [math]\displaystyle{ \omega^{2^{n}} + \bar\omega^{2^{n}} }[/math], we get [math]\displaystyle{ L_0\,=\,\omega+\bar\omega\,=\,4 }[/math] and (since [math]\displaystyle{ \omega\bar\omega\,=\,1 }[/math]) [math]\displaystyle{ 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 }[/math]. Because the [math]\displaystyle{ L_n }[/math] satisfy the same inductive definition as the Lucas sequence numbers [math]\displaystyle{ S_n }[/math], the two sequences must be the same.

Proof of Necessity

If [math]\displaystyle{ p }[/math] is an odd prime and [math]\displaystyle{ 2^p-1 }[/math] is prime then [math]\displaystyle{ S_{p-2} }[/math] is divisible by [math]\displaystyle{ 2^p-1 }[/math].

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

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

Proof of Sufficiency

If [math]\displaystyle{ S_{p-2} }[/math] is divisible by [math]\displaystyle{ 2^p-1 }[/math], then [math]\displaystyle{ 2^p-1 }[/math] is prime.

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

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

LLT DiGraph

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

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

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

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

For each d such that [math]\displaystyle{ d \ \mid \ n }[/math] with [math]\displaystyle{ n = q-1 = 2^s u }[/math] where [math]\displaystyle{ u }[/math] is odd, the number of cycles of length d is:

[math]\displaystyle{ \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) }[/math],

where [math]\displaystyle{ \mu(x) }[/math] is the well-known Moebius function.

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

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

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

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

Universal Initial Values

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

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

Complexity

The Lucas-Lehmer test, when used with the Fast Fourier transform, has a complexity of O(log² N log log N) where N represents the Mersenne number. The complexity can also be represented as O(n² 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

External links

• Wikipedia