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:
- It was done via a massive “prime-hunt” called GIMPS (see below)
- Larger and larger primes are needed for the encryption keys that keep our Amazon account secure
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/
