Mersenne Primes using Lucas Lehmer Primality Test in Python
“Some numbers, even large ones, have no factors — except themselves, of course, and 1. These are called prime numbers because everything they are starts with themselves. They are original, gnarled, unpredictable, the freaks of the number world.”
A Mersenne number is a number which one less than some power of 2 or in simple words of the form (2^n)-1. Also, there is no constraint on ‘n’.
Mersenne Prime is a prime number of the same format that is (2^n)-1 for some integer n (not all). Mersenne primes help in generating large prime numbers which are very helpful while encryption. The largest known prime number 2⁸²⁵⁸⁹⁹³³−1 is a Mersenne prime. So to test the primality of a number, checking each and every possible factor is too old fashioned and time-consuming process, so we will take a different approach.
# function to return a mersenne number
def mersenne_number(p):
return (2**p) - 1Here comes the Lucas Lehmer Test(LLT) in the picture, to test the primality of a Mersenne number. Suppose we have to test the primality of Mp where p is a prime number. It is easy to test the primality of ‘p’ using our usual methods as ‘p’ is exponentially smaller than Mp. Then we have to generate a sequence used in the test which is as follows:
import math# function to generate lucas lehmer series
def lucas_lehmer_series(p):
ll_seq = [4]
if p>2:
for i in range(1, (p-2)+1):
n_i = ((ll_seq[i-1]) ** 2 - 2) % ((2 ** p) - 1)
ll_seq.append(n_i)
return ll_seq
# function to find whether number 'p' is prime or not
def is_prime(number):
if number <= 1 or (number > 2 and number % 2 == 0):
return False
for factor in range(2, int(math.sqrt(number))+1):
if number%factor == 0:
return False
return True
# primality test of mersenne number using above generated series
def ll_prime(p):
if lucas_lehmer_series(p)[-1] == 0:
return True
return False
Mersenne prime will be a prime number only if the last element of the sequence generated is 0 otherwise it is only a Mersenne number.
References:
Some of the sources which I found:
Please let me know in case I have missed something or there is some error.
