Lucas-Lehmer test for Mersenne primes
|
|
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 Mp = 2p− 1 be the Mersenne number to test with p an odd prime. Define a sequence {si} 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, ... Template:OEIS. Then Mp is prime iff
- <math>s_{p-2}\equiv0\pmod{M_p};<math>
otherwise, Mp is composite. The number sp − 2 mod Mp is called the Lucas-Lehmer residue of p.
See also
External links
- MathWorld: Lucas-Lehmer test (http://mathworld.wolfram.com/Lucas-LehmerTest.html)
- GIMPS (The Great Internet Mersenne Prime Search) (http://www.mersenne.org)
- A proof of Lucas-Lehmer test (http://www.jt-actuary.com/lucas-le.htm)ru:Тест Люка-Лемера