Lucas–Lehmer primality test

In mathematics, the Lucas–Lehmer test (LLT) is a primality test for Mersenne numbers. The test was originally developed by Édouard Lucas in 1856 and subsequently improved by Lucas in 1878 and Derrick Henry Lehmer in the 1930s.

The Lucas–Lehmer test works as follows. Let M_p = 2^p − 1 be the Mersenne number to test with p an odd prime. The primality of p can be efficiently checked with a simple algorithm like trial division since p is exponentially smaller than M_p. Define a sequence ${\displaystyle \{s_{i}\}}$ for all i ≥ 0 by

The first few terms of this sequence are 4, 14, 194, 37634, ... (sequence in the OEIS). Then M_p is prime if and only if

The number s_p − 2 mod M_p is called the Lucas–Lehmer residue of p. (Some authors equivalently set s₁ = 4 and test s_p−1 mod M_p). In pseudocode, the test might be written as

Performing the mod M at each iteration ensures that all intermediate results are at most p bits (otherwise the number of bits would double each iteration). The same strategy is used in modular exponentiation.

...
Wikipedia