Editing Lucas–Lehmer primality test (section)

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