lucas lehmer primality test Algorithm
The Lucas-Lehmer primality test algorithm is a primality test specifically designed for testing the primality of Mersenne numbers, which are numbers of the form 2^p - 1, where p is a prime number. This primality test was developed by Édouard Lucas in 1856 and later improved by Derrick Henry Lehmer in the 1930s. The test is based on the properties of Lucas sequences, which are sequences of integers generated by linear recurrence relations. The Lucas-Lehmer test is particularly efficient for Mersenne numbers due to their special structure, and it is the backbone of the search for large prime numbers, mainly because it is much faster than other general-purpose primality tests like the Miller-Rabin or AKS test when dealing with Mersenne numbers.
The algorithm starts by checking if the exponent p is a prime number, as Mersenne numbers with composite exponents are never prime. If p is prime, the test proceeds by initializing a sequence with the value 4 and iteratively applying the recurrence relation S_n = (S_(n-1))^2 - 2 for (p-2) iterations. After the iterations, if the final value of the sequence (S_(p-2)) is divisible by the Mersenne number (2^p - 1), then the Mersenne number is considered prime. Otherwise, it is composite. The success of the Lucas-Lehmer test relies on its simplicity and speed, which has allowed researchers to discover some of the largest known prime numbers. Despite its specialization in Mersenne numbers, the Lucas-Lehmer test remains an essential tool in the field of number theory and computational mathematics.
"""
In mathematics, the Lucas–Lehmer test (LLT) is a primality test for Mersenne numbers.
https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test
A Mersenne number is a number that is one less than a power of two.
That is M_p = 2^p - 1
https://en.wikipedia.org/wiki/Mersenne_prime
The Lucas–Lehmer test is the primality test used by the
Great Internet Mersenne Prime Search (GIMPS) to locate large primes.
"""
# Primality test 2^p - 1
# Return true if 2^p - 1 is prime
def lucas_lehmer_test(p: int) -> bool:
"""
>>> lucas_lehmer_test(p=7)
True
>>> lucas_lehmer_test(p=11)
False
# M_11 = 2^11 - 1 = 2047 = 23 * 89
"""
if p < 2:
raise ValueError("p should not be less than 2!")
elif p == 2:
return True
s = 4
M = (1 << p) - 1
for i in range(p - 2):
s = ((s * s) - 2) % M
return s == 0
if __name__ == "__main__":
print(lucas_lehmer_test(7))
print(lucas_lehmer_test(11))
