Lucas-Lehmer test for Mersenne primes

(Redirected from 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 1878 and subsequently improved by 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. Define a sequence {s_i} for all i ≥ 0 by

<math>

 s_i=
 \left\{
  \begin{matrix}
   4,\qquad\ \,&&\mbox{if }i=0;\ \ \,
  \\
   s_{i-1}^2–2&&\mbox{otherwise.}
  \end{matrix}
 \right.
<math>

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

<math>s_{p-2}\equiv0\pmod{M_p};<math>

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