R@ndom Curve

Searching for Primes
Andres C. Rodriguez 2016-02-04

Yesterday I saw the news that a new largest prime had been found. Geeky piece of news you might say. But it is interesting on a couple of notes:

The prime is $2^{74,207,281}-1$ and it is 22,338,618 digits long. There are people obsessed about comparing things to a Googol (a one followed by 100 zeroes) since the not-named search engine came around. So this prime is a tad larger than a Googol.

Interestingly the Electronic Frontier Foundation has a $150,000 reward for the first person that discovers a 100 million digit prime.

Primes

Prime numbers are the ones that are only divisible by $1$ and by themselves. There is a particular kind of primes called Mersenne Primes that are interesting for various reasons. They all come from the following equation (where $n$ is prime):

\[M_n = 2^n - 1\]

Although all mersenne primes come from the equation, not all numbers of this form are primes (i.e. not all prime $n$ yields a prime). In particular:

\[M_{11} = 2^{11} - 1 = 2047 = 23 × 89\]

Searching for Primes

GIMPS is an organization that distributes code (a program) to thousands of people around the world willing to donate their laptops and desktops computing power in the search for primes. Kind of what SETI does, except the answer is just a little less exciting than discovering E.T. These computers coordinate the humongous arithmetic operations that must be done to verify that a Mersenne number is a prime. After much number crunching, a light might blink in the middle of the night, when one of those thousands of computers performs the final calculation that tells it that indeed it has found a prime. This is exciting enough on its own, but consider that the last biggest prime found was found in 2013, so it means that we have gone 3 years with thousands of computers crunching numbers and we found one prime number larger than the maximum known. And as the press release tells it this last prime was computed months before a human noticed.

Notice in the (partial) table below how the gap is getting larger. Until 1951 it was done by hand. Afterwards computers took over. After 1998, the swarm of GIMPS computers was unbeatable for any one organization.

Number Digits Year Prover / Machine Method / Prover
$2^{17}-1$ 6 1588 Cataldi trial division
$2^{31}-1$ 10 1772 Euler trial division
$(2^{59}-1)/179951$ 13 1867 Landry trial division
$(2^{148}+1)/17$ 44 1951 Ferrier Proth’s theorem
$180(M_{127})^2+1$ 79 1951 EDSAC1 Miller & Wheeler
$M_{2281}$ 687 1952 SWAC Robinson (Oct 9)
$M_{4423}$ 1,332 1961 IBM7090 Hurwitz
$M_{86243}$ 25,962 1982 Cray 1 Slowinski
$M_{756839}$ 227,832 1992 Cray-2 Slowinski & Gage et al. (notes)
$M_{3021377}$ 909,526 1998 Pentium (200 Mhz) [GIMPS, PrimeNet]
$M_{20996011}$ 6,320,430 2003 Pentium (2 GHz) [GIMPS, PrimeNet]
$M_{24036583}$ 7,235,733 2004 Pentium 4 (2.4GHz) [GIMPS, PrimeNet]
$M_{30402457}$ 9,152,052 2005 Pentium 4 (2GHz upgraded to 3GHz) [GIMPS, PrimeNet]
$M_{32582657}$ 9,808,358 2006 Pentium 4 (3 GHz) [GIMPS, PrimeNet]
$M_{43112609}$ 12,978,189 2008 Intel Core 2 Duo E6600 CPU (2.4 GHz) [GIMPS, PrimeNet]
$M_{57885161}$ 17,425,170 2013   [GIMPS, PrimeNet]
$M_{74207281}$ 22,338,618 2016   [GIMPS, PrimeNet]

Why n needs to be a prime?

And for the mathematically inclined, $n$ needs to be a prime because if $n$ was composite (that is $n = a * b$) then:

\[2^{ab} - 1 = (2^a - 1) \cdot (1 + 2^a + 2^{2a} + \ldots + 2^{(b-1)a})\]

Which is equal to:

\[2^{ab} - 1 = (2^b - 1) \cdot (1 + 2^b + 2^{2b} + \ldots + 2^{(a-1)b})\]

Meaning that the Mersenne number is not a prime, if its exponent is not a prime.

References

http://maxwelldemon.com/2012/03/18/prime-phyllotaxis-spirals/