|
|
Lucas-lehmer Test For Mersenne PrimesIn 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 -
s_i= \left\{ \begin{matrix} 4,\qquad\ \,&&\mbox{if }i=0;\ \ \, \\ s_{i-1}^2-2&&\mbox{otherwise.} \end{matrix} \right. The first few terms of this sequence are 4, 14, 194, 37634, ... . Then Mp is prime iff -
otherwise, Mp is composite. The number sp − 2 mod Mp is called the Lucas-Lehmer residue of p. See also External links
|
 |