Lucas–Lehmer test for Mersenne numbers

From Wikipedia, the free encyclopedia

This article is about the Lucas–Lehmer test that only applies to Mersenne numbers. There is also a generalized Lucas–Lehmer test for primality; see 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.

Contents 1 The test 2 See also 3 References 4 External links

[edit] 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

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

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

With FFT implementation, the Lucas–Lehmer test of M_p has the complexity of O(p² log p).

[edit] See also

• Lucas-Lehmer test
• Mersenne's conjecture

[edit] References

• Richard Crandall and Carl Pomerance (2001). Prime Numbers: A Computational Perspective, 1st edition, Springer. ISBN 0387947779.  Section 4.2.1: The Lucas–Lehmer test, pp.167–170.

[edit] External links

• MathWorld: Lucas–Lehmer test
• GIMPS (The Great Internet Mersenne Prime Search)
• A proof of Lucas–Lehmer test
• Lucas–Lehmer Test at MersenneWiki