LucasLehmer

The Lucas–Lehmer test is a primality test for Mersenne numbers of the form M_p = 2^p − 1, where p is a prime. The test determines whether M_p is prime. If p is not prime, M_p is composite, so the test is only applicable when p is prime.

The test has historical roots in the work of Édouard Lucas in the 19th century and was later established in its modern form by Derrick Henry Lehmer in the early 20th century. The standard formulation uses a sequence defined modulo M_p: s_0 = 4, and s_{k+1} = s_k^2 − 2 (mod M_p) for k ≥ 0. Then M_p is prime if and only if s_{p−2} ≡ 0 (mod M_p).

Computationally, the test requires repeated modular squaring and reduction, so its runtime is roughly proportional to p, with the dominant cost coming from arithmetic on p-bit numbers. It is especially used to test large Mersenne numbers and has played a central role in large-prime searches conducted by distributed projects such as the Great Internet Mersenne Prime Search (GIMPS).

When the test yields success, it provides a primality certificate for M_p, confirming that M_p is prime. If the test fails, M_p is composite, and the procedure does not yield a factorization. The Lucas–Lehmer test is specifically tailored to Mersenne numbers; it does not apply to M_p with composite p, since such numbers are always composite.

The Lucas–Lehmer test remains a foundational algorithm in computational number theory, illustrating how specialized modular sequences can determine primality for a particular family of numbers.