Lucas–Lehmer test for Mersenne numbers

Lucas–Lehmer test for Mersenne numbers

:"This article is about the Lucas–Lehmer test (LLT), that only applies to Mersenne numbers. There is also a Lucas-Lehmer-Riesel test for numbers of the form N=k 2^n-1, with 2^n > k, based on the LLT: see Lucas-Lehmer-Riesel test. There is also a Lucas-Lehmer-Reix test for Fermat numbers F_n=2^{2^n}+1, with seed = 5, based on the LLT: see the "External Links". There is also a generalized Lucas–Lehmer test for testing the primality of any number, not based on the LLT: 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 [http://primes.utm.edu/notes/by_year.html] [http://primes.utm.edu/curios/page.php?number_id=135] , 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

: s_i= egin{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, ... OEIS|id=A003010.Then "M""p" is prime iff:s_{p-2}equiv0pmod{M_p}.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, the test might be written:

"// Determine if M"p" = 2"p" − 1 is prime 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

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:

:k equiv (k hbox{ mod } 2^n) + lfloor k/2^n floor 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"n"−1 without using division. For example:

Moreover, since s &times; s will never exceed M2 < 22p, 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"n"−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"2) 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"3). 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"2 log "p" log log "p") or Õ("p"2). [W. N. Colquitt, L. Welsh, Jr. A New Mersenne Prime. "Mathematics of Computation", Vol.56, No.194, pp.867&ndash;870. April 1991. "The use of the FFT speeds up the asymptotic time for the Lucas-Lehmer test for M"p" from O("p"3) to O("p"2 log "p" log log "p") bit operations."]

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

Examples

Suppose we wish to verify that M3 = 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 &larr; ((4 &times; 4) − 2) mod 7 = 0

Because we end with "s" set to zero, M3 is prime.

On the other hand, M11 = 2047 = 23 &times; 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 &larr; ((4 &times; 4) − 2) mod 2047 = 14
* s &larr; ((14 &times; 14) − 2) mod 2047 = 194
* s &larr; ((194 &times; 194) − 2) mod 2047 = 788
* s &larr; ((788 &times; 788) − 2) mod 2047 = 701
* s &larr; ((701 &times; 701) − 2) mod 2047 = 119
* s &larr; ((119 &times; 119) − 2) mod 2047 = 1877
* s &larr; ((1877 &times; 1877) − 2) mod 2047 = 240
* s &larr; ((240 &times; 240) − 2) mod 2047 = 282
* s &larr; ((282 &times; 282) − 2) mod 2047 = 1736

Because "s" is not zero, M11=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: : s_i= egin{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 s_{p-2}equiv0pmod{M_p}.

We begin by noting that {langle}s_i{ angle} is a recurrence relation with a closed-form solution. Define omega = 2 + sqrt{3} and ar{omega} = 2 - sqrt{3}; then we can verify by induction that s_i = omega^{2^i} + ar{omega}^{2^i} for all "i":

:s_0 = omega^{2^0} + ar{omega}^{2^0} = (2 + sqrt{3}) + (2 - sqrt{3}) = 4.:egin{array}{lcl}s_n & = & s_{n-1}^2 - 2 \ & = & left(omega^{2^{n-1 + ar{omega}^{2^{n-1 ight)^2 - 2 \ & = & omega^{2^n} + ar{omega}^{2^n} + 2(omegaar{omega})^{2^{n-1 - 2 \ & = & omega^{2^n} + ar{omega}^{2^n}, \ end{array}where the last step follows from omegaar{omega} = (2 + sqrt{3})(2 - sqrt{3}) = 1. We will use this in both parts.

Sufficiency

In this direction we wish to show that s_{p-2}equiv0pmod{M_p} implies that M_p is prime. We relate a straightforward proof exploiting elementary group theory given by J. W. Bruce [J. W. Bruce. A Really Trivial Proof of the Lucas-Lehmer Test. "The American Mathematical Monthly", Vol.100, No.4, pp.370&ndash;371. April 1993.] as related by Jason Wojciechowski [Jason Wojciechowski. Mersenne Primes, An Introduction and Overview. January 2003. http://wonka.hampshire.edu/~jason/math/smithnum/project.ps] .

Suppose s_{p-2} equiv 0 pmod{M_p}. Then omega^{2^{p-2 + ar{omega}^{2^{p-2 = kM_p for some integer "k", and::egin{array}{rcl}omega^{2^{p-2 & = & kM_p - ar{omega}^{2^{p-2 \left(omega^{2^{p-2 ight)^2 & = & kM_pomega^{2^{p-2 - (omegaar{omega})^{2^{p-2 \omega^{2^{p-1 & = & kM_pomega^{2^{p-2 - 1.quadquadquadquadquad(1) \end{array}

Now suppose "M""p" is composite with nontrivial prime factor "q" > 2 (all Mersenne numbers are odd). Define the set X = {a + bsqrt{3} | a, b in mathbb{Z}_q} with "q"2 elements, where mathbb{Z}_q is the integers mod "q", a finite field. The multiplication operation in X is defined by:

:(a + bsqrt{3})(c + dsqrt{3}) = [(ac + 3bd) hbox{ mod } q] + [(bc + ad) hbox{ mod } q] sqrt{3}.

Since "q" > 2, omega and ar{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 q^2-1 (since 0 has no inverse).

Now, since M_p equiv 0 pmod q, and omega in X, we have kM_pomega^{2^{p-2 = 0 in "X", which by equation (1) gives omega^{2^{p-1 = -1. Squaring both sides gives omega^{2^p} = 1, showing that omega is invertible with inverse omega^{2^{p}-1} and so lies in "X"*, and moreover has an order dividing 2^p. In fact the order must equal 2^p, since omega^{2^{p-1 eq 1 and so the order does not divide 2^{p-1}. Since the order of an element is at most the order (size) of the group, we conclude that 2^p leq q^2 - 1 < q^2. But since "q" is a nontrivial prime factor of M_p, we must have q^2 leq M_p = 2^p-1, yielding the contradiction 2^p < 2^p-1. So M_p is prime.

Necessity

In the other direction, we suppose M_p is prime and show s_{p-2} equiv0pmod{M_p}. We rely on a simplification of a proof by Öystein J. R.Ödseth. [Ö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] First, notice that 3 is a quadratic non-residue mod "M""p", since 2 "p" − 1 for odd "p" > 1 only takes on the value 7 mod 12, and so the Legendre symbol properties tell us (3|M_p) is −1. Euler's criterion then gives us:

: 3^{(M_p-1)/2} equiv -1 pmod{M_p}.

On the other hand, 2 is a quadratic residue mod M_p, since 2^p equiv 1 pmod{M_p} and so 2 equiv 2^{p+1} = left(2^{(p+1)/2} ight)^2 pmod{M_p}. Euler's criterion again gives:

: 2^{(M_p-1)/2} equiv 1 pmod{M_p}.

Next, define sigma = 2sqrt{3}, and define "X"* similarly as before as the multiplicative group of {a + bsqrt{3} | a, b in mathbb{Z}_{M_p}}. We will use the following lemmas:

: (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)

: a^{M_p} equiv a pmod{M_p}

for every integer "a" (Fermat's little theorem)

Then, in the group "X"* we have:

:egin{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 sigma such that omega = (6+sigma)^2/24. Consequently, we can use this to compute omega^{(M_p+1)/2} in the group "X"*:

:egin{array}{lcl}omega^{(M_p+1)/2} & = & (6 + sigma)^{M_p+1}/24^{(M_p+1)/2} \ & = & (6 + sigma)^{M_p}(6 + sigma)/(24 imes 24^{(M_p-1)/2}) \ & = & (6 - sigma)(6 + sigma)/(-24) \ & = & -1.end{array}

where we use the fact that

: 24^{(M_p-1)/2} = (2^{(M_p-1)/2})^3(3^{(M_p-1)/2}) = (1)^3(-1) = -1.

Since M_p equiv 3 pmod 4, all that remains is to multiply both sides of this equation by ar{omega}^{(M_p+1)/4} and use omegaar{omega}=1:

: egin{array}{rcl}omega^{(M_p+1)/2}ar{omega}^{(M_p+1)/4} & = & -ar{omega}^{(M_p+1)/4} \omega^{(M_p+1)/4} + ar{omega}^{(M_p+1)/4} & = & 0 \omega^{(2^p-1+1)/4} + ar{omega}^{(2^p-1+1)/4} & = & 0 \omega^{2^{p-2 + ar{omega}^{2^{p-2 & = & 0 \s_{p-2} & = & 0. \end{array}

Since "s""p"−2 is an integer and is zero in "X"*, it is also zero mod "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. [GIMPS Home Page. Frequently Asked Questions: General Questions: What are Mersenne primes? How are they useful? http://www.mersenne.org/faq.htm#what] 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

* Section 4.2.1: The Lucas–Lehmer test, pp.167&ndash;170.

Notes

External links

* [http://mathworld.wolfram.com/Lucas-LehmerTest.html MathWorld: Lucas–Lehmer test]
* [http://www.mersenne.org GIMPS (The Great Internet Mersenne Prime Search)]
* [http://www.jt-actuary.com/lucas-le.htm A proof of Lucas–Lehmer test (for Mersenne numbers)]
* [http://arxiv.org/abs/0705.3664 A proof of Lucas-Lehmer-Reix test (for Fermat numbers)]
* [http://www.mersennewiki.org/index.php/Lucas-Lehmer_Test Lucas–Lehmer test] at MersenneWiki


Wikimedia Foundation. 2010.

См. также в других словарях:

  • Lucas–Lehmer test — This article is about the generalized Lucas–Lehmer test for primality. There is also a Lucas–Lehmer test that only applies to Mersenne numbers; see Lucas–Lehmer test for Mersenne numbers. In computational number theory, the Lucas–Lehmer test is a …   Wikipedia

  • Lucas-Lehmer-Riesel test — The Lucas Lehmer Riesel test is a primality test for numbers of the form N=k 2^n 1, with 2^n > k. The test was developed by Hans Riesel and it is based on the Lucas–Lehmer test for Mersenne numbers.The algorithmThe algorithm is very similar to… …   Wikipedia

  • Lucas test — may refer to* The Lucas–Lehmer test for primality of general numbers * The Lucas–Lehmer test for Mersenne numbers * Lucas reagent, used to classify alcohols of low molecular weight …   Wikipedia

  • Mersenne conjectures — In mathematics, the Mersenne conjectures concern the characterization of prime numbers of a form called Mersenne primes, meaning prime numbers that are a power of two minus one. Contents 1 Original Mersenne conjecture 2 New Mersenne conjecture …   Wikipedia

  • Mersenne prime — Named after Marin Mersenne Publication year 1536[1] Author of publication Regius, H. Number of known terms 47 Conjectured number of terms Infinite …   Wikipedia

  • Derrick Henry Lehmer — Born February 23, 1905(1905 02 23) Berkeley, California Died May 22, 1991(1991 05 22) (aged&# …   Wikipedia

  • AKS primality test — The AKS primality test (also known as Agrawal–Kayal–Saxena primality test and cyclotomic AKS test) is a deterministic primality proving algorithm created and published by three Indian Institute of Technology Kanpur computer scientists, Manindra… …   Wikipedia

  • Édouard Lucas — François Édouard Anatole Lucas (April 4, 1842 in Amiens October 3, 1891) was a French mathematician. Lucas is known for his study of the Fibonacci sequence. The related Lucas sequence is named after him. He gave a formula for finding the nth term …   Wikipedia

  • Derrick Lehmer — Derrick Henry Lehmer (* 23. Februar 1905 in Berkeley (Kalifornien); † 22. Mai 1991 ebenda) war ein US amerikanischer Mathematiker, spezialisiert auf Zahlentheorie. Inhaltsverzeichnis 1 Leben 2 Werk 3 Schriften …   Deutsch Wikipedia

  • Derrick Henry Lehmer — (* 23. Februar 1905 in Berkeley (Kalifornien); † 22. Mai 1991 ebenda) war ein US amerikanischer Mathematiker, spezialisiert auf Zahlentheorie. Inhaltsverzeichnis 1 Leben 2 Werk 3 Schriften …   Deutsch Wikipedia


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»