Primality and Factorization, The Mersenne Prime Test

The Mersenne Prime Test

The mersenne primes are, by far, the largest primes known. An efficient algorithm, based on the exponent, demonstrates primality.

Let k be the exponent. Thus n = 2^k-1, and we're wondering if n is prime. Remember that k must be prime for n to be prime.

Let e₁ e₂ e₃ etc be the sequence where e₁ = 4, and e_i+1 = e_i² - 2 mod n. The number n is prime iff e_k-1 = 0. This is the mersenne prime test.

Suppose k is even (and greater than 2). Since k is not prime, n is not prime; and each e_i beyond e₁ = 2 mod 3, so e_k-1 is not 0. Hereinafter, we can assume k is odd.

Let z = 2^(k+1)/2, and note that z is a square root of 2 mod n. Let R be the ring of polynomials mod n over the quadratic x²-zx-1. Let a and b be the roots of the quadratic. These lie in Z_n iff the quadratic splits. In either case, a+b = z, and a*b = -1.

Evaluate 2 = z² = (a+b)². The 2ab becomes -2, so a²+b² = 4 = e₁.

Prove by induction that e_i = a^2ⁱ+b^2ⁱ.

The condition e_k-1 = 0 becomes a^{2^k-1} = - b^{2^k-1}. Multiply through by an appropriate power of a and get a^{2^k} = -1. The order of a is 2^k+1.

Get ready to apply the nst prime test. The ring R has n²-1 nonzero elements, which factors into n-1 times n+1. Let s = 2×(n+1), which is certainly larger than the square root of n. It is also easily factored, as it is a power of 2. Set u = a, and u^s = 1, while u^s/2-1 = -2, which is a unit in Z_n. Looks like we're on the right track.

Remember that a^{2^k} = -1, and divide by a, giving aⁿ = b. The polynomial with roots a and aⁿ is the polynomial with roots a and b. This is the aforementioned quadratic, which has integer coefficients. The conditions of the theorem are satisfied, and n is prime. Technically we need to run one trial division, but it's n into n, so we can skip that step.

Conversely, let n be prime. the quadratic has discriminant 6, which is not a residue mod n. First, 2 is a square mod n. To deal with 3, we need k to be odd. Thus n is 1 mod 3, and by reciprocity, 3 is not a square mod n. Since 6 is not a square the quadratic is irreducible, giving a finite field of order n².

Every finite field extension is galois, so there is but one nontrivial field automorphism, which can be expressed as conjugation, i.e. swapping the roots a and b, or as the frobenius automorphism, i.e. raising to the n^th power. Thus, aⁿ has to be a conjugate of a, namely b. Similarly, bⁿ = a.

With this in mind, consider the square of e_k-1. This is 0 iff e_k-1 is 0. Remember that ab = -1.

e_k-1² =
a^{2^k} + b^{2^k} + 2 =
aⁿ×a + bⁿ×b + 2 =
ba + ab + 2 =
0

Procedure

Given an exponent k, derive n = 2^k-1, and run the strong pseudoprime test to see if n is prime. If it is, evaluate e_k-1 to prove n is prime. This entails k iterations of a square mod n. The mod is a simple operation, given the structure of n. Assuming the numbers are in binary, as one would expect from a computer, chop the number into two pieces and add them together. By analogy, reducing a decimal number mod 999 is easy. For example, 292,681 becomes 292+681 = 973 mod 999. So the only difficult step is the square. When k is in the millions, and n is millions of bits long, computers use the fft multiplication algorithm, which runs much faster than k². Using this, the algorithm has complexity k²×log(k).

With this algorithm in hand, mersenne primes are the largest (verified) primes. As of this writing, the largest exponent is 25,964,951. That's almost 8 million decimal digits. If you have some spare cycles on Windows, Unix, or Linux, you can help find the next mersenne prime.