The Lucas-Lehmer Test For Mersenne Primes

The Lucas-Lehmer Test For Mersenne Primes

A Mersenne prime is in the form of 2^S−1. Known Mersenne prime numbers are 2³−1, 2⁵−1, 2⁷−1, 2¹³−1, 2¹⁷−1, 2¹⁹−1, 2³¹−1, 2⁶¹−1, 2⁸⁹−1, 2¹⁰⁷−1 and 2¹²⁷−1. Overall Mersenne primes are efficient in their implementation. This article outlines the the Lucas-Lehmer test to test for a Mersenne prime number. A fast elliptic curve name FourQ uses a prime of 2¹²⁷-1:

Lucas-Lehmer Test

The Lucas–Lehmer test (LLT) is used to test for the primality of Mersenne numbers. It was initally created Edouard Lucas and then enhanced by Derrick Hentry Lehmer. For this test, we initially define u_0=0 and we calculate:

u_{k+1}=(u_k²−2)(mod n)

If u_{s−2}=0 then it is a prime number. Here are some Mersenne Primes:

• 2³−1 Try.
• 2⁵−1 Try.
• 2⁷−1 Try.
• 2¹³−1 Try.
• 2¹⁷−1 Try.
• 2¹⁹−1 Try.
• 2³¹−1 Try.
• 2⁶¹−1 Try.
• 2⁸⁹−1 Try.
• 2¹⁰⁷−1 Try.

The following is the code [here]:

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 [here]:

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

Here is the code:

The Twist

One of the most popular pseudorandom number generators (PRNGs) is the Mersenne Twister. It was created by Makoto Matsumoto and Takuji Nishimur in 1997 and it derives its name from its period length — which the number of values before the sequence repeats — and which is a Mersenne prime.

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 ¹⁹⁹³⁷−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 discovery of 2¹¹²¹³-1 was even given its own post mark:

Since 1997, the Great Internet Mersenne Prime Search (GIMPS) distributed system has been used to find new Mersenne primes .The 51st prime was found in May 2018 and is 2⁸²⁵⁸⁹⁹³³–1. The previous largest is 2⁷⁷²³²⁹¹⁷-1, and and discovered by Jonathan Paceon on Boxing Day in 2017 (and it only the 50th Mersenne prime to be ever found).

A typical value used with the Mersenne Twister is 19,937 (2¹⁹⁹³⁷-1). Overall, PRNGs are deterministic and periodic, but the core strength of the Twister method is the pseudo sequence is unlikely to repeat with 2¹⁹⁹³⁷-1 random numbers:

Overall the method uses sequential states, and where it should not be reasonably possible to know the next state from the current state. But some researchers have shown that “sparse” states can exist, and where there are very few ones or very few zeros, that the next state will also be sparse.

The method has been crititized for using up so many bits (19,937) for the states, and that for security a state value of 256 bits would still be enough, but have a strong effect on the overall performance of the method. A pseudo sequence repeating in 2²⁵⁶ can still be seen as being secure.

Conclusions

PRNGs are deterministic and periodic. With the periodic nature, we repeat the random sequence for the length of all the possible outputs. So if you are watching a slot machine, you might guest that the sequence for the output will eventually repeat. With the Mersenne Twister the period is a massive ²¹⁹⁹³⁷-1, which means that it is unlikely to repeat in a reasonable time frame. An important element is thus the seed value, as, if this can be guessed, it may be possible to replicate the whole sequence.

Another possible attack is on the state machine for generating the sequence, as a PRNG is deterministic. If some of these values are discovered, it may be possible to recreate others from it.

A Cryptographically Secure PRNG (CSPNG) should never repeat its sequence (non-periodic), and uses randomness based on random events (such as the time between system interrupts). Examples of CSPNG include /dev/urandom and CryptGenRandom. A CSPNG should also be non-deterministic.