Mersenne

Git repository

Mersenne primes

Mersenne primes are prime numbers that are $1$ less than a power of $2$. The largest known prime number is often, and currently, a Mersenne prime because they have properties that make it relatively computationally efficient to test their primality.

Mersenne numbers are all numbers of the form $2^n-1$, including those that are not prime.

EFF Cooperative Computing Awards

Through the EFF Cooperative Computing Awards, EFF will confer prizes of:

• $50,000 to the first individual or group who discovers a prime number with at least 1,000,000 decimal digits (awarded Apr. 6, 2000)
• $100,000 to the first individual or group who discovers a prime number with at least 10,000,000 decimal digits (awarded Oct. 22, 2009)
• $150,000 to the first individual or group who discovers a prime number with at least 100,000,000 decimal digits
• $250,000 to the first individual or group who discovers a prime number with at least 1,000,000,000 decimal digits

Source

GIMPS

GIMPS, or the Great Internet Mersenne Prime Search, is volunteer-based distributed computation running the Prime95 software. This software is source-available, however it is not free software as defined by GNU since its use it dictated by a EULA. The EULA includes a clause stating that “$50,000 will be awarded to the discoverer Awardee of the 100,000,000 digit prime.”, out of the $150,000 provided through the EFF. I have not downloaded nor read any GIMPS source code.

GIMPS is responsible for finding every Mersenne prime including and after $2^{1,398,269}-1$.

Lucas-Lehmer primality test

Consider a Mersenne number $2^n-1$, $n$ an odd prime.

$$s_i = \begin{cases} 4 & \textrm{if }i=0;\\s_{i-1}^2 & \textrm{otherwise.}\end{cases}$$$$2^p-1\textrm{ prime if and only if } s_{p-2}\equiv 0\pmod{2^n-1}$$

After a hard derivation, I discovered that this is roughly equivalent to

$$3^{2^p}\equiv 9\pmod{2^p-1}$$

Around a month after I derived this, a new largest Mersenne prime was discovered, and I learned that this was known. My derivation is what this program uses. This can trivially be done in $p$ multiplications. We cannot use Euler’s theorem because we can’t calculate Euler’s totient function because we don’t know the factorization of $2^p-1$.

Helpful theorems

Adapted from mersenne.org

For any Mersenne prime $2^p-1$, $p$ is prime. Proof

Any factor $q$ of $2^p-1$ must be of the form $2kp+1$. Furthermore, $q\equiv\pm 1\pmod{8}$. Finally, $q$ must be prime. Proof

GMP

GMP, GNU Multiple Precision Arithmetic Library, is excellent and this program uses it heavily.

Optimizations

I perform a variable amount of trial divison of values of the form $2kp+1$ before a primality test. Before attempting to divide the candidate by a value, I check to ensure it is $\pm 1\pmod{8}$. Because computers store numbers in base $2$, the least significant word mod $8$ is equal to the entire number mod $8$.

ik2pp1 = mpz_get_ui(k2pp1);
      ik2pp1 = ik2pp1%8;
      if(ik2pp1==1 || ik2pp1==7) {

$$(a^2)\pmod{n} = ((a\pmod{n})^2)\pmod{n}$$

When performing the Lucas Lehmer test, we will take the modulus of the test value often to prevent it from becoming too large.

$$a\pmod{2^n-1}\equiv a\pmod{2^n}+a/2^n$$

where $a$ not too large, and $/$ is integer division.

Because computers store values base $2$, these operations can be performed by simply partitioning the representation of $a$. I’m not sure if this is documented anywhere, but it’s not too difficult to realize. This is significantly faster than GMP’s modulus operator. I perform the operation twice to ensure the result is less than $2^n-1$.

mpz_mul(a, final, final);
mpz_tdiv_q_2exp(q, a, p);
mpz_tdiv_r_2exp(r, a, p);
mpz_add(final, q, r);
mpz_tdiv_q_2exp(q, final, p);
mpz_tdiv_r_2exp(r, final, p);
mpz_add(final, q, r);

Future work

This can be expanded by parallelizing parts of it, as well as adding factoring tests -including P-1 factoring, Quadratic Sieve, and Special number field sieve.

Additionally, formal verification could be implemented to provide proof of the primality of discovered primes.