Lucas-Lehmer Test. For p odd, the Mersenne number 2^p-1 is prime if and only if 2^p-1 divides S(p-1) where S(1) = 4 and S(n+1) = S(n)²-2, for n >= 1.

The theory for this test was initiated by Lucas in the late 1870's and then made into this simple test about 1930 by Lehmer. The sequence S(n) is computed modulo 2^p-1 to save time. This test is ideal for binary computers because the division by 2^p-1 (in binary) can be done using rotation and addition only.