Lucas–Lehmer primality test

This article is about the Lucas–Lehmer test that only applies to Mersenne numbers. For the Lucas–Lehmer test that applies to a natural number n, see Lucas primality test. For the Lucas–Lehmer–Riesel test, see Lucas–Lehmer–Riesel test.

In mathematics, the Lucas–Lehmer test (LLT) is a primality test for Mersenne numbers. The test was originally developed by Édouard Lucas in 1856^[1] 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. The primality of p can be efficiently checked with a simple algorithm like trial division since p is exponentially smaller than M_p. Define a sequence $\{s_i\}$ for all i ≥ 0 by

s_i= \begin{cases} 4 & \text{if }i=0; \\ s_{i-1}^2-2 & \text{otherwise.} \end{cases}

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

s_{p-2} \equiv 0 \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 as

// Determine if Mp = 2p − 1 is prime for p > 2
Lucas–Lehmer(p)
    var s = 4
    var M = 2^p − 1
    repeat p − 2 times:
        s = ((s × s) − 2) mod M
    if s == 0 return PRIME else return COMPOSITE

Performing 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

k \equiv (k\,\bmod\,2^n) + \lfloor k/2^n \rfloor \pmod{2^n - 1}.

This says that the least significant n bits of k plus the remaining bits of k are equivalent to k modulo 2ⁿ−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 2ⁿ−1 is computed without using division. For example,

916 mod 2⁵−1	=	1110010100₂ mod 2⁵−1
	=	11100₂ + 10100₂ mod 2⁵−1
	=	110000₂ mod 2⁵−1
	=	1₂ + 10000₂ mod 2⁵−1
	=	10001₂ mod 2⁵−1
	=	10001₂
	=	17.

Moreover, since s × s will never exceed M² < 2^2p, 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 2ⁿ−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(p²) bit-level or word-level operations to square a p-bit number. Since this happens O(p) times, the total time complexity is O(p³). 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(p² log p log log p) or Õ(p²).^[2] Currently the most efficient known multiplication algorithm, Fürer's algorithm, only needs $p \log p\ 2^{O(\log^* p)}$ time to multiply two p-bit numbers.

By comparison, the most efficient randomized primality test for general integers, the Miller–Rabin primality test, requires O(k n² 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 Õ(n⁶) bit operations in its best known variant and is dramatically slower in practice.

Examples

The Mersenne number M₃ = 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:

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

Since the final value of s is 0, the conclusion is that M₃ is prime.

On the other hand, M₁₁ = 2047 = 23 × 89 is not prime. Again, s is set to 4 but is now updated 11−2 = 9 times:

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

Since the final value of s is not 0, the conclusion is that M₁₁ = 2047 is not prime. Although M₁₁ = 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

s_i= \begin{cases} 4 & \text{if }i=0;\\ s_{i-1}^2-2 & \text{otherwise.} \end{cases}

The goal is to show that M_p is prime iff $s_{p-2} \equiv 0 \pmod{M_p}.$

The sequence ${\langle}s_i{\rangle}$ is a recurrence relation with a closed-form solution. Let $\omega = 2 + \sqrt{3}$ and $\bar{\omega} = 2 - \sqrt{3}$ . It then follows by induction that $s_i = \omega^{2^i} + \bar{\omega}^{2^i}$ for all i:

s_0 = \omega^{2^0} + \bar{\omega}^{2^0} = \left(2 + \sqrt{3}\right) + \left(2 - \sqrt{3}\right) = 4

and

\begin{align} 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{align}

The last step uses $\omega\bar{\omega} = \left(2 + \sqrt{3}\right) \left(2 - \sqrt{3}\right) = 1.$ This closed form is used in both the proof of sufficiency and the proof of necessity.

Sufficiency

The goal is to show that $s_{p-2} \equiv 0 \pmod{M_p}$ implies that $M_p$ is prime. What follows is a straightforward proof exploiting elementary group theory given by J. W. Bruce^[3] as related by Jason Wojciechowski.^[4]

Suppose $s_{p-2} \equiv 0 \pmod{M_p}.$ Then

\omega^{2^{p-2}} + \bar{\omega}^{2^{p-2}} = k M_p

for some integer k, so

\omega^{2^{p-2}} = k M_p - \bar{\omega}^{2^{p-2}}.

Multiplying by $\omega^{2^{p - 2}}$ gives

\left(\omega^{2^{p-2}}\right)^2 = k M_p\omega^{2^{p-2}} - (\omega \bar{\omega})^{2^{p-2}}.

Thus,

\omega^{2^{p-1}} = k M_p\omega^{2^{p-2}} - 1.\qquad\qquad(1)

For a contradiction, suppose M_p is composite, and let q be the smallest prime factor of M_p. Mersenne numbers are odd, so q > 2. Informally,^{[note 1]} let $\mathbb{Z}_q$ be the integers modulo q, and let $X = \left\{a + b \sqrt{3} \mid a, b \in \mathbb{Z}_q\right\}.$ Multiplication in $X$ is defined as

\left(a + \sqrt{3} b\right) \left(c + \sqrt{3} d\right) = [(a c + 3 b d) \,\bmod\,q] + \sqrt{3} [(a d + b c) \,\bmod\,q].

Clearly, this multiplication is closed, i.e. the product of numbers from X is itself in X. The size of X is denoted by $|X|.$

Since q > 2, it follows that $\omega$ and $\bar{\omega}$ are in X.^{[note 2]} The subset of elements in X with inverses forms a group, which is denoted by X* and has size $|X^*|.$ One element in X that does not have an inverse is 0, so $|X^*| \leq |X| - 1 = q^2 - 1.$

Now $M_p \equiv 0 \pmod{q}$ and $\omega \in X$ , so

kM_p\omega^{2^{p-2}} = 0

in X. Then by equation (1),

\omega^{2^{p-1}} = -1

in X, and squaring both sides gives

\omega^{2^p} = 1.

Thus $\omega$ lies in X* and has inverse $\omega^{2^{p}-1}.$ Furthermore the order of $\omega$ divides $2^p.$ However $\omega^{2^{p-1}} \neq 1$ , so the order does not divide $2^{p-1}.$ Thus, the order is exactly $2^p.$

The order of an element is at most the order (size) of the group, so

2^p \leq |X^*| \leq q^2 - 1 < q^2.

But q is the smallest prime factor of the composite $M_p$ , so

q^2 \leq M_p = 2^p-1.

This yields the contradiction $2^p < 2^p-1$ . Therefore $M_p$ is prime.

Necessity

In the other direction, the goal is to show that the primality of $M_p$ implies $s_{p-2} \equiv 0 \pmod{M_p}$ . The following simplified proof is by Öystein J. R. Ödseth.^[5]

Since $2^p - 1 \equiv 7 \pmod{12}$ for odd $p > 1$ , it follows from properties of the Legendre symbol that $(3|M_p) = -1.$ This means that 3 is a quadratic nonresidue modulo $M_p.$ By Euler's criterion, this is equivalent to

3^{\frac{M_p-1}{2}} \equiv -1 \pmod{M_p}.

In contrast, 2 is a quadratic residue modulo $M_p$ since $2^p \equiv 1 \pmod{M_p}$ and so $2 \equiv 2^{p+1} = \left(2^{\frac{p+1}{2}}\right)^2 \pmod{M_p}.$ This time, Euler's criterion gives

2^{\frac{M_p-1}{2}} \equiv 1 \pmod{M_p}.

Combining these two equivalence relations yields

24^{\frac{M_p-1}{2}} \equiv \left(2^{\frac{M_p-1}{2}}\right)^3 \left(3^{\frac{M_p-1}{2}}\right) \equiv (1)^3(-1) \equiv -1 \pmod{M_p}.

Let $\sigma = 2\sqrt{3}$ , and define X as before as the ring $X = \{a + b\sqrt{3} \mid a, b \in \mathbb{Z}_{M_p}\}.$ Then in the ring X, it follows that

\begin{align} (6+\sigma)^{M_p} &= 6^{M_p} + \left(2^{M_p}\right) \left(\sqrt{3}^{M_p}\right) \\ &= 6 + 2 \left(3^{\frac{M_p-1}{2}}\right) \sqrt{3} \\ &= 6 + 2 (-1) \sqrt{3} \\ &= 6 - \sigma, \end{align}

where the first equality uses the Binomial Theorem in a finite field, which is

(x+y)^{M_p} \equiv x^{M_p} + y^{M_p} \pmod{M_p}

and the second equality uses Fermat's little theorem, which is

a^{M_p} \equiv a \pmod{M_p}

for any integer a. The value of $\sigma$ was chosen so that $\omega = \frac{(6+\sigma)^2}{24}.$ Consequently, this can be used to compute $\omega^{\frac{M_p+1}{2}}$ in the ring X as

\begin{align} \omega^{\frac{M_p+1}{2}} &= \frac{(6 + \sigma)^{M_p+1}}{24^{\frac{M_p+1}{2}}} \\ &= \frac{(6 + \sigma) (6 + \sigma)^{M_p}}{24 \cdot 24^{\frac{M_p-1}{2}}} \\ &= \frac{(6 + \sigma) (6 - \sigma)}{-24} \\ &= -1. \end{align}

All that remains is to multiply both sides of this equation by $\bar{\omega}^{\frac{M_p+1}{4}}$ and use $\omega \bar{\omega} = 1$ , which gives

\begin{align} \omega^{\frac{M_p+1}{2}} \bar{\omega}^{\frac{M_p+1}{4}} &= -\bar{\omega}^{\frac{M_p+1}{4}} \\ \omega^{\frac{M_p+1}{4}} + \bar{\omega}^{\frac{M_p+1}{4}} &= 0 \\ \omega^{\frac{2^p-1+1}{4}} + \bar{\omega}^{\frac{2^p-1+1}{4}} &= 0 \\ \omega^{2^{p-2}} + \bar{\omega}^{2^{p-2}} &= 0 \\ s_{p-2} &= 0. \end{align}

Since $s_{p - 2}$ is 0 in X, it is also 0 modulo $M_p.$

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.^[6] 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.

Notes

↑ Formally, let $\mathbb{Z}_q = \mathbb{Z} / q \mathbb{Z}$ and $X = \mathbb{Z}_q[T] / \langle T^2 - 3 \rangle$ .
↑ Formally, $\omega + \langle T^2 - 3 \rangle$ and $\bar{\omega} + \langle T^2 - 3 \rangle$ are in X. By abuse of language $\omega$ and $\bar{\omega}$ are identified with their images in X under the natural ring homomorphism from $\mathbb{Z}[\sqrt{3}]$ to X which sends $\sqrt{3}$ to T.

References

↑ The Largest Known Prime by Year: A Brief History
↑ Colquitt, W. N.; Welsh, L., Jr. (1991), "A New Mersenne Prime", Mathematics of Computation 56 (194): 867–870, doi:10.2307/2008415, 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.
↑ J. W. Bruce (1993). "A Really Trivial Proof of the Lucas–Lehmer Test". The American Mathematical Monthly 100 (4): 370–371. doi:10.2307/2324959.
↑ Jason Wojciechowski. Mersenne Primes, An Introduction and Overview. 2003.
↑ Öystein J. R. Ödseth. A note on primality tests for N = h · 2ⁿ − 1. Department of Mathematics, University of Bergen.
↑ The "Top Ten" Record Primes, The Prime Pages

Crandall, Richard; Pomerance, Carl (2001), "Section 4.2.1: The Lucas–Lehmer test", Prime Numbers: A Computational Perspective (1st ed.), Berlin: Springer, p. 167–170, ISBN 0-387-94777-9

External links

Number-theoretic algorithms

Primality tests	AKS test APR test Baillie–PSW ECPP test Elliptic curve Pocklington Fermat Lucas Lucas–Lehmer Lucas–Lehmer–Riesel Proth's theorem Pépin's Quadratic Frobenius test Solovay–Strassen Miller–Rabin

Prime-generating	Sieve of Atkin Sieve of Eratosthenes Sieve of Sundaram Wheel factorization

Integer factorization	Continued fraction (CFRAC) Dixon's Lenstra elliptic curve (ECM) Euler's Pollard's rho p − 1 p + 1 Quadratic sieve (QS) General number field sieve (GNFS) Special number field sieve (SNFS) Rational sieve Fermat's Shanks' square forms Trial division Shor's

Multiplication	Ancient Egyptian Long Karatsuba Toom–Cook Schönhage–Strassen Fürer's

Discrete logarithm	Baby-step giant-step Pollard rho Pollard kangaroo Pohlig–Hellman Index calculus Function field sieve

Greatest common divisor	Binary Euclidean Extended Euclidean Lehmer's

Modular square root	Cipolla Pocklington's Tonelli–Shanks

Other algorithms	Chakravala Cornacchia LLL Integer square root Modular exponentiation Schoof's

Italics indicate that algorithm is for numbers of special forms

This article is issued from Wikipedia - version of the Friday, February 12, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.