Lucas–Lehmer primality test

thumb | right

In mathematics, the Lucas–Lehmer test (LLT) is a primality test for Mersenne numbers. The test was originally developed by Édouard Lucas in 1878 and subsequently proved by Derrick Henry Lehmer in 1930.

The test

The Lucas–Lehmer test works as follows. Let Mp = 2p − 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 Mp. Define a sequence <math>\{s_i\}</math> for all i ≥ 0 by

:<math>

s_i=

\begin{cases}

4 & \text{if }i=0;

s_{i-1}^2-2 & \text{otherwise.}

\end{cases}

</math>

The first few terms of this sequence are 4, 14, 194, 37634, ... .

Then Mp is prime if and only if

:<math>s_{p-2} \equiv 0 \pmod{M_p}.</math>

The number sp − 2 mod Mp is called the Lucas–Lehmer residue of p. (Some authors equivalently set s1 = 4 and test sp−1 mod Mp). 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 = 2p − 1

repeat p − 2 times:

s = ((s × s) − 2) mod M

if s == 0 return PRIME else return COMPOSITE

Performing the <code>mod M</code> 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.

Alternative starting values

Starting values s0 other than 4 are possible, for instance 10, 52, and others . The Lucas–Lehmer residue calculated with these alternative starting values will still be zero if Mp is a Mersenne prime. However, the terms of the sequence will be different and a non-zero Lucas-Lehmer residue for non-prime Mp will have a different numerical value from the non-zero value calculated when s0 = 4.

It is also possible to use the starting value (2 mod Mp)(3 mod Mp)−1, usually denoted by 2/3 for short. This starting value was often used where suitable in the era of hand computation, including by Lucas in proving M127 prime.

The first few terms of the sequence are 3, 7, 47, ... .

Sign of penultimate term

If sp−2 = 0 mod Mp then the penultimate term is sp−3 = ± 2(p+1)/2 mod Mp. The sign of this penultimate term is called the Lehmer symbol ϵ(s0, p).

In 2000 S.Y. Gebre-Egziabher proved that for the starting value 2/3 and for p ≠ 5 the sign is:

:<math>\epsilon ({2 \over 3},\ p) = (-1) ^ {p-1 \over 2}</math>

That is, ϵ(2/3, p) = +1 if p = 1 (mod 4) and p ≠ 5. that the Lehmer symbols for starting values 4 and 10 when p is not 2 or 5 are related by:

:<math>\epsilon (10,\ p) = \epsilon (4,\ p) \ \times \ (-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}

</math>

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

Sufficiency

The goal is to show that <math>s_{p-2} \equiv 0 \pmod{M_p}</math> implies that <math>M_p</math> is prime. What follows is a straightforward proof exploiting elementary group theory given by J. W. Bruce as related by Jason Wojciechowski.

Suppose <math>s_{p-2} \equiv 0 \pmod{M_p}.</math> Then

:<math>\omega^{2^{p-2 + \bar{\omega}^{2^{p-2 = k M_p</math>

for some integer k, so

:<math>\omega^{2^{p-2 = k M_p - \bar{\omega}^{2^{p-2.</math>

Multiplying by <math>\omega^{2^{p - 2</math> gives

:<math>\left(\omega^{2^{p-2\right)^2 = k M_p\omega^{2^{p-2 - (\omega \bar{\omega})^{2^{p-2.</math>

Thus,

:<math>\omega^{2^{p-1 = k M_p\omega^{2^{p-2 - 1.\qquad\qquad(1)</math>

For a contradiction, suppose Mp is composite, and let q be the smallest prime factor of Mp. Mersenne numbers are odd, so q > 2. Let <math>\mathbb{Z}_q</math> be the integers modulo q, and let <math>X = \left\{a + b \sqrt{3} \mid a, b \in \mathbb{Z}_q\right\}.</math> Multiplication in <math>X</math> is defined as

:<math>\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].</math>

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

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

Now <math>M_p \equiv 0 \pmod{q}</math> and <math>\omega \in X</math>, so

:<math>kM_p\omega^{2^{p-2 = 0</math>

in X.

Then by equation (1),

:<math>\omega^{2^{p-1 = -1</math>

in X, and squaring both sides gives

:<math>\omega^{2^p} = 1.</math>

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

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

:<math>2^p \leq |X^*| \leq q^2 - 1 < q^2.</math>

But q is the smallest prime factor of the composite <math>M_p</math>, so

:<math>q^2 \leq M_p = 2^p-1.</math>

This yields the contradiction <math>2^p < 2^p-1</math>. Therefore, <math>M_p</math> is prime.

Necessity

In the other direction, the goal is to show that the primality of <math>M_p</math> implies <math>s_{p-2} \equiv 0 \pmod{M_p}</math>. The following simplified proof is by Öystein J. Rödseth.

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

:<math>3^{\frac{M_p-1}{2 \equiv -1 \pmod{M_p}.</math>

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

:<math>2^{\frac{M_p-1}{2 \equiv 1 \pmod{M_p}.</math>

Combining these two equivalence relations yields

:<math>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}.</math>

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

:<math>

\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}

</math>

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

: <math>(x+y)^{M_p} \equiv x^{M_p} + y^{M_p} \pmod{M_p}</math>,

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

: <math>a^{M_p} \equiv a \pmod{M_p}</math>

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

:<math>

\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}

</math>

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

:<math>

\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}

</math>

Since <math>s_{p - 2}</math> is 0 in X, it is also 0 modulo <math>M_p.</math>

Applications

The Lucas–Lehmer test was the main primality test used by the Great Internet Mersenne Prime Search (GIMPS) to locate large primes until 2021. This search has been successful in locating many of the largest primes known to date. In 2021, GIMPS switched to an easy-to-error-check variant of Fermat's primality test for locating probable Mersenne primes, and only uses Lucas–Lehmer to verify these probable primes as actual primes.

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.

Lucas–Lehmer primality test

The test

Alternative starting values

Sign of penultimate term

Sufficiency

Necessity

Applications

See also

Notes