Theory
One of the most commonly used version of the Mersenne Twister algorithm is MT19937 and generates a 32-bit word length (using the Mersenne prime of \(2^{19937}ā1\). The method is named after Marin Mersenne and who was a 17th Century French Minim friar. His main contribution included his investigations of prime numbers, along with being seen as the father of acoustics. A Mersenne prime is defined as a prime number that is one less than a power of two. The general form is \(M_n=2^nā1\) where n is an integer.
The largest found is \(2^{77232917}-1\), and which was discovered by Jonathan Paceon on Boxing Day in 2017 (and it only the 50th Mersenne prime to be ever found). Since 1997, the Great Internet Mersenne Prime Search (GIMPS) distributed system has been used to find new Mersenne primes.
For the Lucas-Lehmer test, we initially define \(u_0=0\) and we calculate:
\(u_{k+1}=({u_k}^2-2) \pmod n\)
If \(u_{s-2}=0\) then it is a prime number.
Coding
The following is the code:
import sys s=18 if (len(sys.argv)>1): s=int(sys.argv[1]) if (s>127): sys.exit(1) u=4 n=pow(2,s)-1 print (f"n=2^{s}-1={n}\n") for k in range(1,s-1): u=((u*u)-2) %n print (u,end=' ') if (u==0): print ("\n\nIt is prime") else: print ("\n\nIt is not prime")
And a sample run:
n=2^19-1=524287 14 194 37634 218767 510066 386344 323156 218526 504140 103469 417706 307417 382989 275842 85226 523263 0 It is prime