Lucas-Lehmer primality test

The Lucas-Lehmer test is a deterministic primality test that works only on Mersenne numbers, which have the form two to the power p minus one for an odd prime p. Édouard Lucas developed it in 1878 and Derrick Henry Lehmer proved it correct in 1930. The test starts with the value 4 and repeats a step p minus 2 times, squaring the current value, subtracting 2 and reducing the result modulo the Mersenne number. The Mersenne number is prime exactly when the final value is zero. Reducing at every step keeps each intermediate result within p bits. When squaring uses grade-school multiplication the whole test takes on the order of p cubed bit operations, and faster multiplication lowers that cost. The Great Internet Mersenne Prime Search relied on it as its main primality test for locating very large primes until 2021, after which the project switched to a variant of Fermat's test for probable primes and kept Lucas-Lehmer to confirm them.