In
mathematics, the Lucas–Lehmer test (LLT) is a
primality test
A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating wheth ...
for
Mersenne number
In mathematics, a Mersenne prime is a prime number that is one less than a power of two. That is, it is a prime number of the form for some integer . They are named after Marin Mersenne, a French Minim friar, who studied them in the early 17 ...
s. The test was originally developed by
Édouard Lucas
__NOTOC__
François Édouard Anatole Lucas (; 4 April 1842 – 3 October 1891) was a French mathematician. Lucas is known for his study of the Fibonacci sequence. The related Lucas sequences and Lucas numbers are named after him.
Biography
Luc ...
in 1876 and subsequently improved by
Derrick Henry Lehmer
Derrick Henry "Dick" Lehmer (February 23, 1905 – May 22, 1991), almost always cited as D.H. Lehmer, was an American mathematician significant to the development of computational number theory. Lehmer refined Édouard Lucas' work in the 1930s an ...
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
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
. The primality of ''p'' can be efficiently checked with a simple algorithm like
trial division
Trial division is the most laborious but easiest to understand of the integer factorization algorithms. The essential idea behind trial division tests to see if an integer ''n'', the integer to be factored, can be divided by each number in turn t ...
since ''p'' is exponentially smaller than ''M''
''p''. Define a sequence
for all ''i'' ≥ 0 by
:
The first few terms of this sequence are 4, 14, 194, 37634, ... .
Then ''M''
''p'' is prime if and only if
:
The number ''s''
''p'' − 2 mod ''M''
''p'' is called the Lucas–Lehmer residue of ''p''. (Some authors equivalently set ''s''
1 = 4 and test ''s''
''p''−1 mod ''M''
''p''). In
pseudocode
In computer science, pseudocode is a plain language description of the steps in an algorithm or another system. Pseudocode often uses structural conventions of a normal programming language, but is intended for human reading rather than machine re ...
, the test might be written as
// Determine if ''M''
''p'' = 2
''p'' − 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.
Alternate starting values
Starting values ''s''
0 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 ''M''
''p'' is a Mersenne prime. However, the terms of the sequence will be different and a non-zero Lucas-Lehmer residue for non-prime ''M''
''p'' will have a different numerical value from the non-zero value calculated when ''s''
0 = 4.
It is also possible to use the starting value (2 mod ''M''
''p'')(3 mod ''M''
''p'')
−1, usually denoted by 2/3 for short.
This starting value equals (2
p + 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.
However, some other starting values are only valid for a subset of all possible ''p'', for example ''s''
0 = 3 can be used if ''p'' = 3 (mod 4). This starting value was often used where suitable in the era of hand computation, including by Lucas in proving ''M''
''127'' prime.
The first few terms of the sequence are 3, 7, 47, ... .
Sign of penultimate term
If ''s''
''p''−2 = 0 mod ''M''
''p'' then the penultimate term is ''s''
''p''−3 = ± 2
(''p''+1)/2 mod ''M''
''p''. The sign of this penultimate term is called the Lehmer symbol ϵ(''s''
0, ''p'').
In 2000 S.Y. Gebre-Egziabher proved that for the starting value 2/3 and for ''p'' ≠ 5 the sign is:
:
That is, ϵ(2/3, ''p'') = +1 iff ''p'' = 1 (mod 4) and p ≠ 5.
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:
:
That is, ϵ(4, ''p'') × ϵ(10, ''p'') = 1 iff ''p'' = 5 or 7 (mod 8) and p ≠ 2, 5.
OEIS sequence shows ϵ(4, ''p'') for each Mersenne prime ''M''
''p''.
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
:
This says that the least significant ''n'' bits of ''k'' plus the remaining bits of ''k'' are equivalent to ''k'' modulo 2
''n''−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
''n''−1 is computed without using division. For example,
Moreover, since
s × s
will never exceed M
2 < 2
2p, this simple technique converges in at most 1 ''p''-bit addition (and possibly a carry from the ''p''th bit to the 1st bit), which can be done in linear time. This algorithm has a small exceptional case. It will produce 2
''n''−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
A multiplication algorithm is an algorithm (or method) to multiply two numbers. Depending on the size of the numbers, different algorithms are more efficient than others. Efficient multiplication algorithms have existed since the advent of the de ...
used to square ''s'' at each step. The simple "grade-school" algorithm for multiplication requires
O(''p''
2) 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''
3). A more efficient multiplication algorithm is the
Schönhage–Strassen algorithm
The Schönhage–Strassen algorithm is an asymptotically fast multiplication algorithm for large integers. It was developed by Arnold Schönhage and Volker Strassen in 1971.A. Schönhage and V. Strassen,Schnelle Multiplikation großer Zahlen, ''C ...
, which is based on the
Fast Fourier transform
A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). Fourier analysis converts a signal from its original domain (often time or space) to a representation in th ...
. It only requires O(''p'' log ''p'' log log ''p'') time to square a ''p''-bit number. This reduces the complexity to O(''p''
2 log ''p'' log log ''p'') or Õ(''p''
2). An even more efficient multiplication algorithm,
Fürer's algorithm
A multiplication algorithm is an algorithm (or method) to multiply two numbers. Depending on the size of the numbers, different algorithms are more efficient than others. Efficient multiplication algorithms have existed since the advent of the de ...
, only needs
time to multiply two ''p''-bit numbers.
By comparison, the most efficient randomized primality test for general integers, the
Miller–Rabin primality test
The Miller–Rabin primality test or Rabin–Miller primality test is a probabilistic primality test: an algorithm which determines whether a given number is likely to be prime, similar to the Fermat primality test and the Solovay–Strassen prima ...
, requires O(''k'' ''n''
2 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
6) bit operations in its best known variant and is extremely slow even for relatively small values.
Examples
The Mersenne number M
3 = 2
3−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:
* s ← ((4 × 4) − 2) mod 7 = 0.
Since the final value of ''s'' is 0, the conclusion is that M
3 is prime.
On the other hand, M
11 = 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
11 = 2047 is not prime. Although M
11 = 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
:
The goal is to show that ''M''
''p'' is prime
iff
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is bicond ...
The sequence
is a
recurrence relation
In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...
with a
closed-form solution. Let
and
. It then follows by
induction that
for all ''i'':
:
and
:
The last step uses
This closed form is used in both the proof of sufficiency and the proof of necessity.
Sufficiency
The goal is to show that
implies that
is prime. What follows is a straightforward proof exploiting elementary
group theory
In abstract algebra, group theory studies the algebraic structures known as groups.
The concept of a group is central to abstract algebra: other well-known algebraic structures, such as rings, fields, and vector spaces, can all be seen as ...
given by J. W. Bruce as related by Jason Wojciechowski.
Suppose
Then
:
for some integer ''k'', so
:
Multiplying by
gives
:
Thus,
:
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,
[Formally, let and .] let
be the integers modulo ''q'', and let
Multiplication in
is defined as
:
Clearly, this multiplication is closed, i.e. the product of numbers from ''X'' is itself in ''X''. The size of ''X'' is denoted by
Since ''q'' > 2, it follows that
and
are in ''X''.
[Formally, and are in ''X''. By abuse of language and are identified with their images in ''X'' under the natural ring homomorphism from to ''X'' which sends to ''T''.] The subset of elements in ''X'' with inverses forms a group, which is denoted by ''X''* and has size
One element in ''X'' that does not have an inverse is 0, so
Now
and
, so
:
in ''X''.
Then by equation (1),
:
in ''X'', and squaring both sides gives
:
Thus
lies in ''X''* and has inverse
Furthermore, the
order of
divides
However
, so the order does not divide
Thus, the order is exactly
The order of an element is at most the order (size) of the group, so
:
But ''q'' is the smallest prime factor of the composite
, so
:
This yields the contradiction
. Therefore,
is prime.
Necessity
In the other direction, the goal is to show that the primality of
implies
. The following simplified proof is by Öystein J. Rödseth.
Since
for odd
, it follows from
properties of the Legendre symbol that
This means that 3 is a
quadratic nonresidue
In number theory, an integer ''q'' is called a quadratic residue modulo ''n'' if it is congruent to a perfect square modulo ''n''; i.e., if there exists an integer ''x'' such that:
:x^2\equiv q \pmod.
Otherwise, ''q'' is called a quadratic ...
modulo
By
Euler's criterion In number theory, Euler's criterion is a formula for determining whether an integer is a quadratic residue modulo a prime. Precisely,
Let ''p'' be an odd prime and ''a'' be an integer coprime to ''p''. Then
:
a^ \equiv
\begin
\;\;\,1\pmod& \tex ...
, this is equivalent to
:
In contrast, 2 is a
quadratic residue
In number theory, an integer ''q'' is called a quadratic residue modulo ''n'' if it is congruent to a perfect square modulo ''n''; i.e., if there exists an integer ''x'' such that:
:x^2\equiv q \pmod.
Otherwise, ''q'' is called a quadratic n ...
modulo
since
and so
This time, Euler's criterion gives
:
Combining these two equivalence relations yields
:
Let
, and define ''X'' as before as the ring
Then in the ring ''X'', it follows that
:
where the first equality uses the
Binomial Theorem in a finite field, which is
:
,
and the second equality uses
Fermat's little theorem
Fermat's little theorem states that if ''p'' is a prime number, then for any integer ''a'', the number a^p - a is an integer multiple of ''p''. In the notation of modular arithmetic, this is expressed as
: a^p \equiv a \pmod p.
For example, if = ...
, which is
:
for any integer ''a''. The value of
was chosen so that
Consequently, this can be used to compute
in the ring ''X'' as
:
All that remains is to multiply both sides of this equation by
and use
, which gives
:
Since
is 0 in ''X'', it is also 0 modulo
Applications
The Lucas–Lehmer test is one of the main primality tests used by the
Great Internet Mersenne Prime Search
The Great Internet Mersenne Prime Search (GIMPS) is a collaborative project of volunteers who use freely available software to search for Mersenne prime numbers.
GIMPS was founded in 1996 by George Woltman, who also wrote the Prime95 client a ...
(GIMPS) to locate large primes. This search has been successful in locating many of the largest primes known to date.
The "Top Ten" Record Primes
The Prime Pages The PrimePages is a website about prime numbers maintained by Chris Caldwell at the University of Tennessee at Martin.
The site maintains the list of the "5,000 largest known primes", selected smaller primes of special forms, and many "top twenty" ...
The test is considered valuable because it can probably 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 In mathematics, Pépin's test is a primality test, which can be used to determine whether a Fermat number is prime. It is a variant of Proth's test. The test is named for a French mathematician, Théophile Pépin.
Description of the test
Let F_n ...
for any Fermat number
In mathematics, a Fermat number, named after Pierre de Fermat, who first studied them, is a positive integer of the form
:F_ = 2^ + 1,
where ''n'' is a non-negative integer. The first few Fermat numbers are:
: 3, 5, 17, 257, 65537, 42949672 ...
can only be used on a much smaller set of very large numbers before reaching computational limits.
See also
* Mersenne's conjecture
* Lucas–Lehmer–Riesel test
Notes
References
*
External links
*
GIMPS (The Great Internet Mersenne Prime Search)
A proof of Lucas–Lehmer–Reix test (for Fermat numbers)
Lucas–Lehmer test
at MersenneWiki
{{DEFAULTSORT:Lucas-Lehmer Primality Test
Primality tests
Mersenne primes