Editing Lucas–Lehmer primality test

{{Short description|Test if a Mersenne number is prime}}
{{about|the Lucas–Lehmer test that applies only to Mersenne numbers|the Lucas–Lehmer test that applies to a natural number ''n''|Lucas primality test|the Lucas–Lehmer–Riesel test|Lucas–Lehmer–Riesel test}}

In [[mathematics]], the '''Lucas–Lehmer test''' ('''LLT''') is a [[primality test]] for [[Mersenne prime|Mersenne number]]s. The test was originally developed by [[Édouard Lucas]] in 1878<ref>{{cite journal|last=Jaroma|first=John H.|year=2004|title=Note on the Lucas–Lehmer Test|journal=Bulletin of the Irish Mathematical Society|publisher=Irish Mathematical Society|volume=54|issue=2|page=63|doi=10.33232/BIMS.0054.63.72 |s2cid=16831811 |url=https://www.irishmathsoc.org/bull54/M5402.pdf}}</ref> and subsequently proved by [[Derrick Henry Lehmer]] in 1930.

==The test==
The Lucas–Lehmer test works as follows. Let ''M''<sub>''p''</sub>&nbsp;=&nbsp;2<sup>''p''</sup>&nbsp;&minus;&nbsp;1 be the Mersenne number to test with ''p'' an odd [[Prime number|prime]]. The primality of ''p'' can be efficiently checked with a simple algorithm like [[trial division]] since ''p'' is exponentially smaller than ''M''<sub>''p''</sub>. 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, ... {{OEIS|id=A003010}}.
Then ''M''<sub>''p''</sub> is prime if and only if
:<math>s_{p-2} \equiv 0 \pmod{M_p}.</math>
The number ''s''<sub>''p''&nbsp;&minus;&nbsp;2</sub>&nbsp;mod&nbsp;''M''<sub>''p''</sub> is called the '''Lucas–Lehmer residue''' of ''p''. (Some authors equivalently set ''s''<sub>1</sub>&nbsp;=&nbsp;4 and test ''s''<sub>''p''&minus;1</sub> mod ''M''<sub>''p''</sub>). In [[pseudocode]], the test might be written as

 // Determine if ''M''<sub>''p''</sub> = 2<sup>''p''</sup> &minus; 1 is prime for ''p'' > 2
 '''Lucas–Lehmer'''(p)
     '''var''' s = 4
     '''var''' M = 2<sup>''p''</sup> &minus; 1
     '''repeat''' p &minus; 2 times:
         s = ((s &times; s) &minus; 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]].

===Alternate starting values===

Starting values ''s''<sub>0</sub> other than 4 are possible, for instance 10, 52, and others {{OEIS|id=A018844}}.<ref name="Jansen">{{cite thesis |last=Jansen |first=B.J.H. |title=Mersenne primes and class field theory |pages=iii–iv |date=2012 |type=Doctoral thesis |institution=Leiden University |url=https://openaccess.leidenuniv.nl/handle/1887/20310 |access-date=2018-12-17}}</ref> The Lucas–Lehmer residue calculated with these alternative starting values will still be zero if ''M''<sub>''p''</sub> is a Mersenne prime. However, the terms of the sequence will be different and a non-zero Lucas-Lehmer residue for non-prime ''M''<sub>''p''</sub> will have a different numerical value from the non-zero value calculated when ''s''<sub>0</sub>&nbsp;=&nbsp;4.

It is also possible to use the starting value (2&nbsp;mod&nbsp;''M''<sub>''p''</sub>)(3&nbsp;mod&nbsp;''M''<sub>''p''</sub>)<sup>−1</sup>, usually denoted by 2/3 for short.<ref name="Jansen"/> This starting value equals (2<sup>p</sup>&nbsp;+&nbsp;1)&nbsp;/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.<ref name="Jansen"/> However, some other starting values are only valid for a subset of all possible ''p'', for example ''s''<sub>0</sub>&nbsp;=&nbsp;3 can be used if ''p''&nbsp;=&nbsp;3&nbsp;(mod&nbsp;4).<ref>{{cite journal |first=Raphael M. |last=Robinson |date=1954 |title=Mersenne and Fermat numbers |journal=Proc. Amer. Math. Soc. |volume=5 |issue=5 |pages=842–846 |doi=10.1090/S0002-9939-1954-0064787-4|doi-access=free }}</ref> This starting value was often used where suitable in the era of hand computation, including by Lucas in proving ''M''<sub>''127''</sub> prime.<ref>{{cite tech report |url=https://core.ac.uk/download/pdf/12758.pdf?repositoryId=17 |first=Guy |last=Haworth |title=Mersenne numbers |page=20 |year=1990 |access-date=2018-12-17}}</ref>
The first few terms of the sequence are 3, 7, 47, ... {{OEIS|A001566}}.

===Sign of penultimate term===

If ''s''<sub>''p''−2</sub>&nbsp;=&nbsp;0&nbsp;mod&nbsp;''M''<sub>''p''</sub> then the penultimate term is ''s''<sub>''p''−3</sub>&nbsp;=&nbsp;±&nbsp;2<sup>(''p''+1)/2</sup>&nbsp;mod&nbsp;''M''<sub>''p''</sub>. The sign of this penultimate term is called the Lehmer symbol ϵ(''s''<sub>0</sub>,&nbsp;''p'').

In 2000 S.Y. Gebre-Egziabher proved that for the starting value 2/3 and for ''p''&nbsp;≠&nbsp;5 the sign is:
:<math>\epsilon ({2 \over 3},\ p) = (-1) ^ {p-1 \over 2}</math>
That is, ϵ(2/3,&nbsp;''p'')&nbsp;=&nbsp;+1 if ''p''&nbsp;=&nbsp;1&nbsp;(mod&nbsp;4) and p&nbsp;≠&nbsp;5.<ref name="Jansen"/>

The same author also proved [[George Woltman|Woltman]]'s conjecture<ref>{{cite conference |url=http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15190/pdf/DagSemRep-306.pdf |conference=Algorithms and Number Theory |editor-first1=J. |editor-last1=Buhler |editor-first2=H. |editor-last2=Niederreiter |editor-first3=M.E. |editor-last3=Pohst |title=Woltman's conjecture on the Lucas-Lehmer test |author-first=H. W. |author-last=Lenstra, Jr. |author-link=Hendrik Lenstra |date=2001-05-13 |page=20 |access-date=2024-10-16}}</ref> 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) ^ {{(p+1)(p+3)} \over 8}</math>
That is, ϵ(4,&nbsp;''p'')&nbsp;×&nbsp;ϵ(10,&nbsp;''p'')&nbsp;=&nbsp;1 if ''p''&nbsp;=&nbsp;5&nbsp;or&nbsp;7&nbsp;(mod&nbsp;8) and p&nbsp;≠&nbsp;2,&nbsp;5.<ref name="Jansen"/>

OEIS sequence {{OEIS link|A123271}} shows ϵ(4,&nbsp;''p'') for each Mersenne prime ''M''<sub>''p''</sub>.

== Time complexity ==

In the algorithm as written above, there are two expensive operations during each iteration: the multiplication <code>s&nbsp;&times;&nbsp;s</code>, and the <code>mod M</code> operation. The <code>mod M</code> operation can be made particularly efficient on standard binary computers by observing that

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

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

{|
|916 mod 2<sup>5</sup>&minus;1 || = || 1110010100<sub>2</sub> mod 2<sup>5</sup>&minus;1
|-
|                              || = || ((916 mod 2<sup>5</sup>) + int(916 ÷ 2<sup>5</sup>)) mod 2<sup>5</sup>&minus;1
|-
|                              || = || (10100<sub>2</sub> + 11100<sub>2</sub>) mod 2<sup>5</sup>&minus;1
|-
|                              || = || 110000<sub>2</sub> mod 2<sup>5</sup>&minus;1
|-
|                              || = || (10000<sub>2</sub> + 1<sub>2</sub>) mod 2<sup>5</sup>&minus;1
|-
|                              || = || 10001<sub>2</sub> mod 2<sup>5</sup>&minus;1
|-
|                              || = || 10001<sub>2</sub>
|-
|                              || = || 17.
|}

Moreover, since <code>s &times; s</code> will never exceed M<sup>2</sup> < 2<sup>2p</sup>, 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<sup>''n''</sup>&minus;1 for a multiple of the modulus rather than the correct value of&nbsp;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 [[big O notation|O]](''p''<sup>2</sup>) 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''<sup>3</sup>). 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''<sup>2</sup> log ''p'' log log ''p'') or Õ(''p''<sup>2</sup>).<ref>{{Citation |last1=Colquitt |first1=W. N. |last2=Welsh |first2=L. Jr. |title=A New Mersenne Prime |journal=Mathematics of Computation |volume=56 |issue=194 |pages=867–870 |year=1991 |quote=The use of the FFT speeds up the asymptotic time for the Lucas–Lehmer test for M<sub>''p''</sub> from O(''p''<sup>3</sup>) to O(''p''<sup>2</sup> log ''p'' log log ''p'') bit operations. |doi=10.2307/2008415|jstor=2008415 |doi-access=free }}</ref> An even more efficient multiplication algorithm, [[Fürer's algorithm]], only needs <math>p \log p\ 2^{O(\log^* p)}</math> 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''<sup>2</sup> 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, and is similarly fast in practice. 

The most efficient deterministic primality test for any ''n''-digit number, the [[AKS primality test]], requires Õ(n<sup>6</sup>) bit operations in its best known variant and is extremely slow even for relatively small values.

== Examples ==

The Mersenne number M<sub>3</sub> = 2<sup>3</sup>−1 = 7 is prime. The Lucas–Lehmer test verifies this as follows. Initially ''s'' is set to 4 and then is updated 3&minus;2&nbsp;=&nbsp;1 time:

* s ← ((4 &times; 4) &minus; 2) mod 7 = 0.

Since the final value of ''s'' is&nbsp;0, the conclusion is that M<sub>3</sub> is prime.

On the other hand, M<sub>11</sub>&nbsp;=&nbsp;2047&nbsp;=&nbsp;23&nbsp;&times;&nbsp;89 is not prime. Again, ''s'' is set to 4 but is now updated 11&minus;2&nbsp;=&nbsp;9 times:

* s ← ((4 &times; 4) &minus; 2) mod 2047 = 14
* s ← ((14 &times; 14) &minus; 2) mod 2047 = 194
* s ← ((194 &times; 194) &minus; 2) mod 2047 = 788
* s ← ((788 &times; 788) &minus; 2) mod 2047 = 701
* s ← ((701 &times; 701) &minus; 2) mod 2047 = 119
* s ← ((119 &times; 119) &minus; 2) mod 2047 = 1877
* s ← ((1877 &times; 1877) &minus; 2) mod 2047 = 240
* s ← ((240 &times; 240) &minus; 2) mod 2047 = 282
* s ← ((282 &times; 282) &minus; 2) mod 2047 = 1736

Since the final value of ''s'' is not&nbsp;0, the conclusion is that M<sub>11</sub>&nbsp;=&nbsp;2047 is not prime. Although M<sub>11</sub>&nbsp;=&nbsp;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
:<math>
  s_i=
   \begin{cases}
    4 & \text{if }i=0;\\
    s_{i-1}^2-2 & \text{otherwise.}
   \end{cases}
 </math>
The goal is to show that ''M''<sub>''p''</sub> is prime [[iff]] <math>s_{p-2} \equiv 0 \pmod{M_p}.</math>

The sequence <math>{\langle}s_i{\rangle}</math> is a [[recurrence relation]] with a [[closed-form solution]]. Let <math>\omega = 2 + \sqrt{3}</math> and <math>\bar{\omega} = 2 - \sqrt{3}</math>. It then follows by [[mathematical induction|induction]] that <math>s_i = \omega^{2^i} + \bar{\omega}^{2^i}</math> for all ''i'':

:<math>s_0 = \omega^{2^0} + \bar{\omega}^{2^0} = \left(2 + \sqrt{3}\right) + \left(2 - \sqrt{3}\right) = 4</math>
and
:<math>
\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}
</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<ref>{{cite journal |first=J. W. |last=Bruce |title=A Really Trivial Proof of the Lucas–Lehmer Test |journal=The American Mathematical Monthly |volume=100 |issue=4 |pages=370–371 |year=1993 |doi=10.2307/2324959|jstor=2324959 }}</ref> as related by Jason Wojciechowski.<ref>Jason Wojciechowski. [https://web.archive.org/web/20110722232101/http://wonka.hampshire.edu/~jason/math/smithnum/project.ps Mersenne Primes, An Introduction and Overview]. 2003.</ref>

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 ''M''<sub>''p''</sub> is composite, and let ''q'' be the smallest prime factor of ''M''<sub>''p''</sub>. Mersenne numbers are odd, so ''q''&nbsp;>&nbsp;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><ref group="note">Formally, let <math>\mathbb{Z}_q = \mathbb{Z} / q \mathbb{Z}</math> and <math>X = \mathbb{Z}_q[T] / \langle T^2 - 3 \rangle</math>.</ref>

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''&nbsp;>&nbsp;2, it follows that <math>\omega</math> and <math>\bar{\omega}</math> are in ''X''.<ref group="note">Formally, <math>\omega + \langle T^2 - 3 \rangle</math> and <math>\bar{\omega} + \langle T^2 - 3 \rangle</math> are in ''X''.  By abuse of language <math>\omega</math> and <math>\bar{\omega}</math> are identified with their images in ''X'' under the natural ring homomorphism from <math>\mathbb{Z}[\sqrt{3}] </math> to ''X'' which sends <math>\sqrt{3}</math> to ''T''.</ref> 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 (group theory)|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.<ref name="Rodseth">{{cite journal|last=Rödseth|first=Öystein J.|title=A note on primality tests for N=h·2^n−1|journal=BIT Numerical Mathematics|volume=34|number=3|date=1994|pages=451–454|doi=10.1007/BF01935653|s2cid=120438959 |url=http://folk.uib.no/nmaoy/papers/luc.pdf|archive-url=https://web.archive.org/web/20160306082833/http://folk.uib.no/nmaoy/papers/luc.pdf|archive-date=March 6, 2016}}</ref>

Since <math>2^p - 1 \equiv 7 \pmod{12}</math> for odd <math>p > 1</math>, it follows from [[Legendre symbol#Properties of the Legendre symbol|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 [[Proofs of Fermat's little theorem#Proofs using the binomial theorem|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.<ref>[http://primes.utm.edu/largest.html#biggest The "Top Ten" Record Primes], [[The Prime Pages]]</ref> In 2021, GIMPS switched to an even faster 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.

== See also ==
* [[Mersenne's conjecture]]
* [[Lucas–Lehmer–Riesel test]]

== Notes ==
<references group="note"/>

== References ==
{{reflist|2}}
* {{citation |first1=Richard |last1=Crandall |author-link=Richard Crandall |first2=Carl |last2=Pomerance |author-link2=Carl Pomerance |year=2001 |title=Prime Numbers: A Computational Perspective |publisher=Springer |location=Berlin |edition=1st |isbn=0-387-94777-9 |chapter=Section 4.2.1: The Lucas–Lehmer test |pages=167–170}}

== External links ==
* {{MathWorld |urlname=Lucas-LehmerTest |title=Lucas–Lehmer test}}
* [http://www.mersenne.org GIMPS (The Great Internet Mersenne Prime Search)]
* [https://arxiv.org/abs/0705.3664 A proof of Lucas–Lehmer–Reix test (for Fermat numbers)]
* [https://web.archive.org/web/20160216234138/http://www.mersennewiki.org/index.php/Lucas-Lehmer_Test Lucas–Lehmer test] at MersenneWiki

{{number theoretic algorithms}}

{{DEFAULTSORT:Lucas-Lehmer Primality Test}}
[[Category:Primality tests]]
[[Category:Mersenne primes]]