Lucas–Lehmer test for Mersenne numbers

This article is about the Lucas–Lehmer test that only applies to Mersenne numbers. There is also a generalized Lucas–Lehmer test for primality; see Lucas–Lehmer test.

In mathematics, the Lucas–Lehmer test is a primality test for Mersenne numbers. The test was originally developed by Edouard Lucas in 1856 [1][2], and subsequently improved by Lucas in 1878 and Derrick Henry Lehmer in the 1930s.

The test

The Lucas-Lehmer test works as follows. Let M_p = 2^p− 1 be the Mersenne number to test with p an odd prime (because p is exponentially smaller than M_p, we can use a simple algorithm like trial division for establishing its primality). Define a sequence {s_i} for all i ≥ 0 by

Failed to parse (Missing texvc executable; please see math/README to configure.): s_i= \begin{cases} 4 & \mbox{if }i=0; \\ s_{i-1}^2-2 & \mbox{otherwise.} \end{cases}

The first few terms of this sequence are 4, 14, 194, 37634, ... (sequence A003010 in OEIS). Then M_p is prime iff

Failed to parse (Missing texvc executable; please see math/README to configure.): s_{p-2}\equiv0\pmod{M_p};

The number s_{p − 2} mod M_p is called the Lucas–Lehmer residue of p. (Some authors equivalently set s₁=4 and test s_p−1 mod M_p). In pseudocode, the test might be written:

// Determine if Mp = 2p − 1 is prime
Lucas-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 COMPOSITE

By performing the mod M at each iteration, we ensure that all intermediate results are at most p bits (otherwise the number of bits would double each iteration). It is exactly the same strategy employed 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 the following simple property:

Failed to parse (Missing texvc executable; please see math/README to configure.): k \equiv (k \hbox{ mod } 2^n) + \lfloor k/2^n \rfloor \pmod{2^n - 1}

.

In other words, if we take the least significant n bits of k, and add the remaining bits of k, and then do this repeatedly until at most n bits remain, we can compute the remainder after dividing k by the Mersenne number 2ⁿ−1 without using division. For example:

Moreover, since s × s will never exceed M² < 2^2p, this simple technique converges in at most 2 p-bit additions, which can be done in linear time. As a small exceptional case, the above algorithm may produce 2ⁿ−1 for a multiple of the modulus, rather than the correct value of zero; this should be accounted for.

With the modulus out of the way, the asymptotic complexity of the algorithm depends only on the multiplication algorithm used to square s at each step. The simple "grade-school" algorithm for multiplication requires O(p²) bit-level or word-level operations to square a p-bit number, and since we do this O(p) times, the total time complexity is O(p³). The most efficient known multiplication method, the Schönhage-Strassen algorithm based on the Fast Fourier transform, requires O(p log p log log p) time to square a p-bit number, reducing the complexity to O(p² log p log log p) or Õ(p²).^[1]

By comparison, the most efficient randomized primality test for general integers, the Miller-Rabin primality test, takes O(k p² log p log log p) bit operations using FFT multiplication, where k is the number of iterations and is related to the error rate. This is a constant factor difference for constant k, but in practice the cost of doing many iterations and other differences lead to worse performance for Miller-Rabin. The most efficient deterministic primality test for general integers, the AKS primality test, requires Õ(p⁶) bit operations in its best known variant and is dramatically slower in practice.

Examples

Suppose we wish to verify that M₃ = 7 is prime using the Lucas-Lehmer test. We start out with s set to 4 and then update it 3−2 = 1 time, taking the results mod 7:

• s ← ((4 × 4) − 2) mod 7 = 0

Because we end with s set to zero, M₃ is prime.

On the other hand, M₁₁ = 2047 = 23 × 89 is not prime. To show this, we start with s set to 4 and update it 11−2 = 9 times, taking the results mod 2047:

• s ← ((4 × 4) − 2) mod 2047 = 14
• s ← ((14 × 14) − 2) mod 2047 = 194
• s ← ((194 × 194) − 2) mod 2047 = 788
• s ← ((788 × 788) − 2) mod 2047 = 701
• s ← ((701 × 701) − 2) mod 2047 = 119
• s ← ((119 × 119) − 2) mod 2047 = 1877
• s ← ((1877 × 1877) − 2) mod 2047 = 240
• s ← ((240 × 240) − 2) mod 2047 = 282
• s ← ((282 × 282) − 2) mod 2047 = 1736

Because s is not zero, M₁₁=2047 is not prime. Notice that we learn nothing about the factors of 2047, only its Lucas–Lehmer residue, 1736.

Proof of correctness

Lehmer's original proof of the correctness of this test is complex, so we'll depend upon more recent refinements. Recall the definition:

Failed to parse (Missing texvc executable; please see math/README to configure.): s_i= \begin{cases} 4 & \mbox{if }i=0; \\ s_{i-1}^2-2 & \mbox{otherwise.} \end{cases}

Then our theorem is that M_p is prime iff Failed to parse (Missing texvc executable; please see math/README to configure.): s_{p-2}\equiv0\pmod{M_p}.

We begin by noting that Failed to parse (Missing texvc executable; please see math/README to configure.): {\langle}s_i{\rangle}

is a recurrence relation with a closed-form solution. Define Failed to parse (Missing texvc executable; please see math/README to configure.): \omega = 2 + \sqrt{3}
and Failed to parse (Missing texvc executable; please see math/README to configure.): \bar{\omega} = 2 - \sqrt{3}

then we can verify by induction that Failed to parse (Missing texvc executable; please see math/README to configure.): s_i = \omega^{2^i} + \bar{\omega}^{2^i}

for all i:

Failed to parse (Missing texvc executable; please see math/README to configure.): s_0 = \omega^{2^0} + \bar{\omega}^{2^0} = (2 + \sqrt{3}) + (2 - \sqrt{3}) = 4.

Failed to parse (Missing texvc executable; please see math/README to configure.): \begin{array}{lcl}s_n & = & s_{n-1}^2 - 2 \\ & = & \left(\omega^{2^{n-1}} + \bar{\omega}^{2^{n-1}}\right)^2 - 2 \\ & = & \omega^{2^n} + \bar{\omega}^{2^n} + 2(\omega\bar{\omega})^{2^{n-1}} - 2 \\ & = & \omega^{2^n} + \bar{\omega}^{2^n}, \\ \end{array}

where the last step follows from Failed to parse (Missing texvc executable; please see math/README to configure.): \omega\bar{\omega} = (2 + \sqrt{3})(2 - \sqrt{3}) = 1 . We will use this in both parts.

Sufficiency

In this direction we wish to show that Failed to parse (Missing texvc executable; please see math/README to configure.): s_{p-2}\equiv0\pmod{M_p}

implies that Failed to parse (Missing texvc executable; please see math/README to configure.): M_p
is prime. We relate a straightforward proof exploiting elementary group theory given by J. W. Bruce[2] as related by Jason Wojciechowski[3]. 


Suppose Failed to parse (Missing texvc executable; please see math/README to configure.): s_{p-2} \equiv 0 \pmod{M_p}
. Then Failed to parse (Missing texvc executable; please see math/README to configure.): \omega^{2^{p-2}} + \bar{\omega}^{2^{p-2}} = kM_p

for some integer k, and:

Failed to parse (Missing texvc executable; please see math/README to configure.): \begin{array}{rcl} \omega^{2^{p-2}} & = & kM_p - \bar{\omega}^{2^{p-2}} \\ \left(\omega^{2^{p-2}}\right)^2 & = & kM_p\omega^{2^{p-2}} - (\omega\bar{\omega})^{2^{p-2}} \\ \omega^{2^{p-1}} & = & kM_p\omega^{2^{p-2}} - 1.\quad\quad\quad\quad\quad(1) \\ \end{array}

Now suppose Mp is composite with nontrivial prime factor q > 2 (all Mersenne numbers are odd). Define the set Failed to parse (Missing texvc executable; please see math/README to configure.): X = \{a + b\sqrt{3} | a, b \in \mathbb{Z}_q\}

with q2 elements, where Failed to parse (Missing texvc executable; please see math/README to configure.): \mathbb{Z}_q
is the integers mod q, a finite field. The multiplication operation in X is defined by:

Failed to parse (Missing texvc executable; please see math/README to configure.): (a + b\sqrt{3})(c + d\sqrt{3}) = [(ac + 3bd) \hbox{ mod } q] + [(bc + ad) \hbox{ mod } q]\sqrt{3}

.


Since q > 2, Failed to parse (Missing texvc executable; please see math/README to configure.): \omega

and Failed to parse (Missing texvc executable; please see math/README to configure.): \bar{\omega}
are in X. Any product of two numbers in X is in X, but it's not a group under multiplication because not every element x has an inverse y such that xy = 1. If we consider only the elements that have inverses, we get a group X* of size at most Failed to parse (Missing texvc executable; please see math/README to configure.): q^2-1
(since 0 has no inverse).

Now, since Failed to parse (Missing texvc executable; please see math/README to configure.): M_p \equiv 0 \pmod q
, and Failed to parse (Missing texvc executable; please see math/README to configure.): \omega \in X
, we have Failed to parse (Missing texvc executable; please see math/README to configure.): kM_p\omega^{2^{p-2}} = 0

in X, which by equation (1) gives Failed to parse (Missing texvc executable; please see math/README to configure.): \omega^{2^{p-1}} = -1

. Squaring both sides gives Failed to parse (Missing texvc executable; please see math/README to configure.): \omega^{2^p} = 1
, showing that Failed to parse (Missing texvc executable; please see math/README to configure.): \omega

is invertible with inverse Failed to parse (Missing texvc executable; please see math/README to configure.): \omega^{2^{p}-1}
and so lies in X*, and moreover has an order dividing Failed to parse (Missing texvc executable; please see math/README to configure.): 2^p

. In fact the order must equal Failed to parse (Missing texvc executable; please see math/README to configure.): 2^p
,  since Failed to parse (Missing texvc executable; please see math/README to configure.): \omega^{2^{p-1}} \neq 1

and so the order does not divide Failed to parse (Missing texvc executable; please see math/README to configure.): 2^{p-1}

. Since the order of an element is at most the order (size) of the group, we conclude that Failed to parse (Missing texvc executable; please see math/README to configure.): 2^p \leq q^2 - 1 < q^2
. But since q is a nontrivial prime factor of Failed to parse (Missing texvc executable; please see math/README to configure.): M_p
, we must have Failed to parse (Missing texvc executable; please see math/README to configure.): q^2 \leq M_p = 2^p-1
, yielding the contradiction Failed to parse (Missing texvc executable; please see math/README to configure.): 2^p < 2^p-1
. So Failed to parse (Missing texvc executable; please see math/README to configure.): M_p

is prime.

Necessity

In the other direction, we suppose Failed to parse (Missing texvc executable; please see math/README to configure.): M_p

is prime and show Failed to parse (Missing texvc executable; please see math/README to configure.): s_{p-2} \equiv0\pmod{M_p}

. We rely on a simplification of a proof by Öystein J. R.
Ödseth.[4] First, notice that 3 is a quadratic non-residue mod Failed to parse (Missing texvc executable; please see math/README to configure.): M_p
, since Failed to parse (Missing texvc executable; please see math/README to configure.): 2^p - 1

for odd p>1 only takes on the value 7 mod 12, and so the Legendre symbol properties tell us Failed to parse (Missing texvc executable; please see math/README to configure.): (3|M_p)
is -1. Euler's criterion then gives us:

• Failed to parse (Missing texvc executable; please see math/README to configure.): 3^{(M_p-1)/2} \equiv -1 \pmod{M_p}

.


On the other hand, 2 is a quadratic residue mod Failed to parse (Missing texvc executable; please see math/README to configure.): M_p
, since Failed to parse (Missing texvc executable; please see math/README to configure.): 2^p \equiv 1 \pmod{M_p}

and so Failed to parse (Missing texvc executable; please see math/README to configure.): 2 \equiv 2^{p+1} = \left(2^{(p+1)/2}\right)^2 \pmod{M_p}

. Euler's criterion again gives:

• Failed to parse (Missing texvc executable; please see math/README to configure.): 2^{(M_p-1)/2} \equiv 1 \pmod{M_p}

.


Next, define Failed to parse (Missing texvc executable; please see math/README to configure.): \sigma = 2\sqrt{3}
, and define X* similarly as before as the multiplicative group of Failed to parse (Missing texvc executable; please see math/README to configure.): \{a + b\sqrt{3} | a, b \in \mathbb{Z}_{M_p}\}
. We will use the following lemmas:

• Failed to parse (Missing texvc executable; please see math/README to configure.): (x+y)^{M_p} \equiv x^{M_p} + y^{M_p} \pmod{M_p}

(from Proofs of Fermat's little theorem#Proof_using_the_binomial_theorem)

• Failed to parse (Missing texvc executable; please see math/README to configure.): a^{M_p} \equiv a \pmod{M_p}

for every integer a (Fermat's little theorem)

Then, in the group X* we have:

Failed to parse (Missing texvc executable; please see math/README to configure.): \begin{array}{lcl} (6+\sigma)^{M_p} & = & 6^{M_p} + (2^{M_p})(\sqrt{3}^{M_p}) \\ & = & 6 + 2(3^{(M_p-1)/2})\sqrt{3} \\ & = & 6 + 2(-1)\sqrt{3} \\ & = & 6 - \sigma. \end{array}

We chose Failed to parse (Missing texvc executable; please see math/README to configure.): \sigma

such that Failed to parse (Missing texvc executable; please see math/README to configure.): \omega = (6+\sigma)^2/24

. Consequently, we can use this to compute Failed to parse (Missing texvc executable; please see math/README to configure.): \omega^{(M_p+1)/2}

in the group X*:

Failed to parse (Missing texvc executable; please see math/README to configure.): \begin{array}{lcl} \omega^{(M_p+1)/2} & = & (6 + \sigma)^{M_p+1}/24^{(M_p+1)/2} \\ & = & (6 + \sigma)^{M_p}(6 + \sigma)/(24 \times 24^{(M_p-1)/2}) \\ & = & (6 - \sigma)(6 + \sigma)/(-24) \\ & = & -1. \end{array}

where we use the fact that

• Failed to parse (Missing texvc executable; please see math/README to configure.): 24^{(M_p-1)/2} = (2^{(M_p-1)/2})^3(3^{(M_p-1)/2}) = (1)^3(-1) = -1.

Since Failed to parse (Missing texvc executable; please see math/README to configure.): M_p \equiv 3 \pmod 4
, all that remains is to multiply both sides of this equation by Failed to parse (Missing texvc executable; please see math/README to configure.): \bar{\omega}^{(M_p+1)/4}

and use Failed to parse (Missing texvc executable; please see math/README to configure.): \omega\bar{\omega}=1

Failed to parse (Missing texvc executable; please see math/README to configure.): \begin{array}{rcl} \omega^{(M_p+1)/2}\bar{\omega}^{(M_p+1)/4} & = & -\bar{\omega}^{(M_p+1)/4} \\ \omega^{(M_p+1)/4} + \bar{\omega}^{(M_p+1)/4} & = & 0 \\ \omega^{(2^p-1+1)/4} + \bar{\omega}^{(2^p-1+1)/4} & = & 0 \\ \omega^{2^{p-2}} + \bar{\omega}^{2^{p-2}} & = & 0 \\ s_{p-2} & = & 0. \\ \end{array}




Since Failed to parse (Missing texvc executable; please see math/README to configure.): s_{p-2}

is an integer and is zero in X*, it is also zero mod Failed to parse (Missing texvc executable; please see math/README to configure.): M_p

.

Applications

The Lucas-Lehmer test is the primality test used by the Great Internet Mersenne Prime Search to locate large primes, and has been successful in locating many of the largest primes known to date.[5] They consider it valuable for finding very large primes because Mersenne numbers are considered somewhat more likely to be prime than randomly chosen odd integers of the same size. Additionally, the test is considered valuable because it can provably test a very large number for primality within affordable time and (in contrast to the equivalently fast Pépin's Test for any Fermat number) can be tried on a large search space of numbers with the required form before reaching computational limits.

See also

• Lucas-Lehmer test
• Mersenne's conjecture

References

• Richard Crandall and Carl Pomerance (2001). Prime Numbers: A Computational Perspective, 1st edition, Springer. ISBN 0387947779.  Section 4.2.1: The Lucas–Lehmer test, pp.167–170.

1. ^ W. N. Colquitt, L. Welsh, Jr. A New Mersenne Prime. Mathematics of Computation, Vol.56, No.194, pp.867–870. April 1991. "The use of the FFT speeds up the asymptotic time for the Lucas-Lehmer test for M_p from O(p³) to O(p² log p log log p) bit operations."
2. ^ J. W. Bruce. A Really Trivial Proof of the Lucas-Lehmer Test. The American Mathematical Monthly, Vol.100, No.4, pp.370–371. April 1993.
3. ^ Jason Wojciechowski. Mersenne Primes, An Introduction and Overview. January 2003. http://wonka.hampshire.edu/~jason/math/smithnum/project.ps
4. ^ Öystein J. R. Ödseth. A note on primality tests for N = h · 2n − 1. Department of Mathematics, University of Bergen. http://www.uib.no/People/nmaoy/papers/luc.pdf
5. ^ GIMPS Home Page. Frequently Asked Questions: General Questions: What are Mersenne primes? How are they useful? http://www.mersenne.org/faq.htm#what

External links

• MathWorld: Lucas–Lehmer test
• GIMPS (The Great Internet Mersenne Prime Search)
• A proof of Lucas–Lehmer test
• Lucas–Lehmer test at MersenneWiki

da:Lucas-Lehmer


es:Test de Lucas-Lehmer para números de Mersenne
fr:Test de primalité de Lucas-Lehmer pour les nombres de Mersenne
he:מבחן לוקאס-להמר למספרי מרסן
pl:Test Lucasa-Lehmera
ru:Тест Люка — Лемера
fi:Lucasin ja Lehmerin alkulukutesti Mersennen luvuille