Lucas–Lehmer primality test explained

In mathematics, the Lucas–Lehmer test (LLT) is a primality test for Mersenne numbers. The test was originally developed by Édouard Lucas in 1878[1] 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

\{si\}

for all i ≥ 0 by

si= \begin{cases} 4&ifi=0; \\

2-2
s
i-1

&otherwise. \end{cases}

The first few terms of this sequence are 4, 14, 194, 37634, ... .Then Mp is prime if and only if

sp-2\equiv0\pmod{Mp}.

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 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.

Alternate starting values

Starting values s0 other than 4 are possible, for instance 10, 52, and others .[2] 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.[2] This starting value equals (2p + 1) /3, the Wagstaff number with exponent p.

Starting values like 4, 10, and 2/3 are universal, that is, they are valid for all (or nearly all) p. There are infinitely many additional universal starting values.[2] However, some other starting values are only valid for a subset of all possible p, for example s0 = 3 can be used if p = 3 (mod 4).[3] This starting value was often used where suitable in the era of hand computation, including by Lucas in proving M127 prime.[4] 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 ϵ(s0p).

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

\epsilon({2\over3},p)=(-1)p-1

That is, ϵ(2/3, p) = +1 if p = 1 (mod 4) and p ≠ 5.[2]

The same author also proved that the Lehmer symbols for starting values 4 and 10 when p is not 2 or 5 are related by:

\epsilon(10,p)=\epsilon(4,p)  x (-1){(p+1)(p+3)\over8}

That is, ϵ(4, p) × ϵ(10, p) = 1 if p = 5 or 7 (mod 8) and p ≠ 2, 5.[2]

OEIS sequence shows ϵ(4, p) for each Mersenne prime Mp.

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\bmod2n)+\lfloork/2n\rfloor\pmod{2n-1}.

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

916 mod 25-1 = 11100101002 mod 25-1
= ((916 mod 25) + int(916 ÷ 25)) mod 25-1
= (101002 + 111002) mod 25-1
= 1100002 mod 25-1
= (100002 + 12) mod 25-1
= 100012 mod 25-1
= 100012
= 17.

Moreover, since s &times; s will never exceed M2 < 22p, 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 2n-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(p2) bit-level or word-level operations to square a p-bit number. Since this happens O(p) times, the total time complexity is O(p3). 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(p2 log p log log p) or Õ(p2). An even more efficient multiplication algorithm, Fürer's algorithm, only needs

plog

O(log*p)
p 2
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 n2 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 Õ(n6) bit operations in its best known variant and is extremely slow even for relatively small values.

Examples

The Mersenne number M3 = 23−1 = 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:

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

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

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

si= \begin{cases} 4&ifi=0;\\

2-2
s
i-1

&otherwise. \end{cases}

The goal is to show that Mp is prime iff

sp-2\equiv0\pmod{Mp}.

The sequence

{\langle}si{\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

si=

2i
\omega

+

2i
\bar{\omega}
for all i:

s0=

20
\omega

+

20
\bar{\omega}

=\left(2+\sqrt{3}\right)+\left(2-\sqrt{3}\right)=4

and

\begin{align} sn &=

2
s
n-1

-2\\ &=

2n-1
\left(\omega

+

2n-1
\bar{\omega}

\right)2-2\\ &=

2n
\omega

+

2n
\bar{\omega}

+

2n-1
2(\omega\bar{\omega})

-2\\ &=

2n
\omega

+

2n
\bar{\omega}

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

sp-2\equiv0\pmod{Mp}

implies that

Mp

is prime. What follows is a straightforward proof exploiting elementary group theory given by J. W. Bruce[5] as related by Jason Wojciechowski.[6]

Suppose

sp-2\equiv0\pmod{Mp}.

Then
2p-2
\omega

+

2p-2
\bar{\omega}

=kMp

for some integer k, so
2p-2
\omega

=kMp-

2p-2
\bar{\omega}

.

Multiplying by
2p
\omega
gives
2p-2
\left(\omega

\right)2=k

2p-2
M
p\omega

-(\omega

2p-2
\bar{\omega})

.

Thus,
2p-1
\omega

=k

2p-2
M
p\omega

-1.       (1)

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

Zq

be the integers modulo q, and let

X=\left\{a+b\sqrt{3}\mida,b\inZq\right\}.

Multiplication in

X

is defined as

\left(a+\sqrt{3}b\right)\left(c+\sqrt{3}d\right)=[(ac+3bd)\bmodq]+\sqrt{3}[(ad+bc)\bmodq].

[7]

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.[8] 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=q2-1.

Now

Mp\equiv0\pmod{q}

and

\omega\inX

, so
2p-2
kM
p\omega

=0

in X.Then by equation (1),
2p-1
\omega

=-1

in X, and squaring both sides gives
2p
\omega

=1.

Thus

\omega

lies in X* and has inverse
2p-1
\omega

.

Furthermore, the order of

\omega

divides

2p.

However
2p-1
\omega

1

, so the order does not divide

2p-1.

Thus, the order is exactly

2p.

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

2p\leq|X*|\leqq2-1<q2.

But q is the smallest prime factor of the composite

Mp

, so

q2\leqMp=2p-1.

This yields the contradiction

2p<2p-1

. Therefore,

Mp

is prime.

Necessity

In the other direction, the goal is to show that the primality of

Mp

implies

sp-2\equiv0\pmod{Mp}

. The following simplified proof is by Öystein J. Rödseth.[9]

Since

2p-1\equiv7\pmod{12}

for odd

p>1

, it follows from properties of the Legendre symbol that

(3|Mp)=-1.

This means that 3 is a quadratic nonresidue modulo

Mp.

By Euler's criterion, this is equivalent to
Mp-1
2
3

\equiv-1\pmod{Mp}.

In contrast, 2 is a quadratic residue modulo

Mp

since

2p\equiv1\pmod{Mp}

and so

2\equiv2p+1=

p+1
2
\left(2

\right)2\pmod{Mp}.

This time, Euler's criterion gives
Mp-1
2
2

\equiv1\pmod{Mp}.

Combining these two equivalence relations yields

Mp-1
2
24

\equiv

Mp-1
2
\left(2

\right)3

Mp-1
2
\left(3

\right)\equiv(1)3(-1)\equiv-1\pmod{Mp}.

Let

\sigma=2\sqrt{3}

, and define X as before as the ring

X=\{a+b\sqrt{3}\mida,b\in

Z
Mp

\}.

Then in the ring X, it follows that

\begin{align}

Mp
(6+\sigma)

&=

Mp
6

+

Mp
\left(2

\right)

Mp
\left(\sqrt{3}

\right)\\ &=6+2

Mp-1
2
\left(3

\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

Mp
(x+y)

\equiv

Mp
x

+

Mp
y

\pmod{Mp}

,

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

Mp
a

\equiva\pmod{Mp}

for any integer a. The value of

\sigma

was chosen so that

\omega=

(6+\sigma)2
24

.

Consequently, this can be used to compute
Mp+1
2
\omega
in the ring X as

\begin{align}

Mp+1
2
\omega

&=

(6+
Mp+1
\sigma)
Mp+1
2
24

\\ &=

(6+\sigma)(6+
Mp
\sigma)
24
Mp-1
2
24

\\ &=

(6+\sigma)(6-\sigma)
-24

\\ &=-1. \end{align}

All that remains is to multiply both sides of this equation by

Mp+1
4
\bar{\omega}
and use

\omega\bar{\omega}=1

, which gives

\begin{align}

Mp+1
2
\omega
Mp+1
4
\bar{\omega}

&=

Mp+1
4
-\bar{\omega}

\\

Mp+1
4
\omega

+

Mp+1
4
\bar{\omega}

&=0\\

2p-1+1
4
\omega

+

2p-1+1
4
\bar{\omega}

&=0\\

2p-2
\omega

+

2p-2
\bar{\omega}

&=0\\ sp-2&=0. \end{align}

Since

sp

is 0 in X, it is also 0 modulo

Mp.

Applications

The Lucas–Lehmer test is one of the main primality tests used by the Great Internet Mersenne Prime Search (GIMPS) to locate large primes. This search has been successful in locating many of the largest primes known to date.[10] 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.

See also

Notes

  1. Jaroma. John H.. 2004. Note on the Lucas–Lehmer Test. Bulletin of the Irish Mathematical Society. Irish Mathematical Society. 54. 2. 63. 10.33232/BIMS.0054.63.72 . 16831811 .
  2. Jansen . B.J.H. . Mersenne primes and class field theory . iii . 2012 . Doctoral thesis . Leiden University . 2018-12-17.
  3. Raphael M. . Robinson . 1954 . Mersenne and Fermat numbers . Proc. Amer. Math. Soc. . 5 . 5 . 842–846 . 10.1090/S0002-9939-1954-0064787-4. free .
  4. Mersenne numbers . Guy . Haworth . 20 . 1990 . 2018-12-17.
  5. J. W. . Bruce . A Really Trivial Proof of the Lucas–Lehmer Test . The American Mathematical Monthly . 100 . 4 . 370–371 . 1993 . 10.2307/2324959. 2324959 .
  6. Jason Wojciechowski. Mersenne Primes, An Introduction and Overview. 2003.
  7. Formally, let

    Zq=Z/qZ

    and

    X=Zq[T]/\langleT2-3\rangle

    .
  8. Formally,

    \omega+\langleT2-3\rangle

    and

    \bar{\omega}+\langleT2-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

    Z[\sqrt{3}]

    to X which sends

    \sqrt{3}

    to T.
  9. Rödseth. Öystein J.. A note on primality tests for N=h·2^n−1. BIT Numerical Mathematics. 34. 3. 1994. 451–454. 10.1007/BF01935653. 120438959 . https://web.archive.org/web/20160306082833/http://folk.uib.no/nmaoy/papers/luc.pdf. March 6, 2016.
  10. http://primes.utm.edu/largest.html#biggest The "Top Ten" Record Primes

External links