Lucas-Lehmer test

Fragment in French of the Lucas-Lehmer Test.

In mathematics, the Lucas-Lehmer test is a test used to determine whether a certain Mersenne number M_p is prime. The test was developed by Edouard Lucas in 1878 and subsequently improved by Derrick Henry Lehmer in the 1930s.

The test

The Lucas-Lehmer test consists of the following: let M_p = 2^p− 1 the Mersenne number to test with p odd prime. Define the sequence {s_i} for all i ≥ 0 according to:

si={4,Yeah.i=0;si− − 12− − 2Otherwise.{displaystyle s_{i}=left{{begin{matrix}4,qquad , expose{mbox{si }i=0; ,\s_{i-1}^{2}-2 stranger{mbox{in case otherwise}}}}end{matrix}}right. !

The first terms of this sequence are 4, 14, 194, 37634,... (sequence A003010 in OEIS). Then, M_p is prime if and only if

sp− − 2≡ ≡ 0(modMp);{displaystyle s_{p-2}equiv 0{pmod {M_{p}}};}

Otherwise, M_p is composite. The number s_{p − 2} mod M_p is called the Lucas–Lehmer residue of p.

An implementation using the Schönhage–Strassen fast multiplication algorithm, itself based on the fast Fourier transform, gives the Lucas–Lehmer test a complexity of O(n² log n log log n), where n is the length of the number.