A Brief History

The largest known prime today
is the 22,338,618 digit Mersenne prime 2^{74207281}-1 found in
January 2016, but how big have the "largest known primes" been
historically? Historically,
how have these primes been found? We will briefly discuss each of these
questions below.

- Before Electronic Computers
- Table of the Record Prime by Year

- The Age of Electronic Computers
- Epilogue: No more predictions
- The First Billion Digit Prime

If NPR sent you here looking for the French Monk Marin Mersenne's prime conjecture and its errors, see this link

Many early writers felt (incorrectly) that if *p* was prime, then so
was M_{p} = 2^{p}-1. These numbers, now
called the Mersenne Numbers, were the
focus of most of the early searches for large primes. The early history
of these numbers is strewn with many false claims of primality, even by such
notables as Mersenne, Leibniz, and Euler. So we give credit to our first
record holder with some doubt:

by 1588 Pietro Cataldi had correctly verified that 2^{17}-1 = 131071 and 2^{19}-1 = 524287 are both prime [Cataldi1603].

But Cataldi also had incorrectly stated 2^{n}-1 was also prime
for each of 23, 29, 31 and 37. This is interesting because Cataldi made
his discoveries by constructing what Shanks calls "the first extensive table
of primes--up to 750" [Shanks78 p14]. These
tables are big enough to show 2^{19}-1 is prime (its square root is
approximately 724) but *not* large enough to handle these four larger
numbers!

Note: Some writers (e.g., [Picutti1989]
and [BS96, p309]) include
the primes 8191=2^{13}-1 (before 1458, Codice Palatino 573) and 131071=2^{17}-1
(1460, Codex Ottb. Lat 3307) in their list of records. But we omit them
for lack of evidence that they were proven primes at that time, rather than
just lucky guesses.

In 1640 Fermat showed that if *p* is an odd prime, then all prime divisors
of 2^{p}-1 have the form 2*kp*+1. He then quickly
showed Cataldi was wrong about 23 (which has the factor 47 with *k*=1)
and 37 (factor 223 at *k*=3). Finally, in 1738, Euler showed Cataldi
was also wrong about 29 by finding the divisor 233. Here, using Fermat's
result, *k*=4. This is just the second number to try using Fermat's
result as *k*=2 and *k*=3 yield composites (so I would guess Fermat
also knew of this factor). Note that Cataldi's errors were shown with
small factors found in Cataldi's own table of primes, and none took more than
two trial divisions!

Euler gives us the first clear record (except perhaps for the date) by proving Cataldi was correct about 31:

by 1772 Euler had used clever reasoning and trial division to show 2^{31}-1 = 2147483647 is prime.

The actual date must be between 28 October 1752 when Euler sent a letter
to Goldbach [text from Euler
Archive] stating that he was uncertain about this number (even though he
had earlier listed it as prime) and 1772 when a letter [text] was published
from Euler to Bernoulli stating he proved 2^{31}-1 prime by showing
all prime divisors of 2^{31}-1
must have one of the two forms 248*n*+1 and 248*n*+63, and then dividing
by all such primes less than 46339 [Dickson19 pp18-19]. This
requires a simple theorem which is stronger
than Fermat's result above. (Euler had listed 2^{31}-1 a prime
as early as 1732,
but he did so along with 2^{41}-1 and 2^{47}-1
both of which were composite [translation].)

Note: Some writers (e.g., [BS96, p309]) include
the primes 999999000001 (1851, "found" by Looff) and 67280421310721
(1 Jan. 1855, Clausen) in their tables. The first appeared in a table
of Looff with a question mark, but Reuschle [Reuschle1856,
pp.3,18] claims Looff had proved it prime. Thomas Clausen provided the
factorization 274177*67280421310721 of 2^{64}+1 in a letter to Gauss
dated 1 Jan 1855 stating both factors were prime [Biermann1964]. But
it remains a claim without a method.

By 1867 Landry had found a larger prime, still by trial division, as a factor
of 2^{59}-1 (namely (2^{59}-1)/179951 = 3203431780337), this
prime held the record longer than any other **non**-Mersenne would (before
or after his discovery). However all such efforts were to be eclipsed
by a new mathematical discovery, so we pause for a moment to summarize all
record primes (that I know about) before modern computers. (In the long
run, it is always the mathematics that decide how large of prime we can find.)

Number | Digits | Year | Prover | Method |
---|---|---|---|---|

2^{17}-1 |
6 | 1588 | Cataldi | trial division |

2^{19}-1 |
6 | 1588 | Cataldi | trial division |

2^{31}-1 |
10 | 1772 | Euler | trial division++ |

(2^{59}-1)/179951 |
13 | 1867 | Landry | trial division++ |

2^{127}-1 |
39 | 1876 | Lucas | Lucas sequences |

(2^{148}+1)/17 |
44 | 1951 | Ferrier | Proth's theorem |

By 1876 Lucas had developed a clever test to determine if Mersenne numbers were prime. His method was later made even simpler by Lehmer in the 1930's, and is still used to discover the record primes!

In 1876 Lucas proved that 2^{127}-1 = 170141183460469231731687303715884105727 was prime.

"This remained the largest known prime until 1951" [HW79 p16] And this
record, which stood for 75 years, may stand forever as the largest prime found *by
hand calculations*.

In 1951 Ferrier used a mechanical desk calculator and techniques based on partial inverses of Fermat's little theorem (see the pages on finding and proving primes) to slightly better this record by finding a 44 digit prime:

In 1951 Ferrier found the prime (2^{148}+1)/17 = 20988936657440586486151264256610222593863921.

With this record we end the period before electronic computers, for in this same year a new record of 79 digits was to be set by computer.

Note: It is quite difficult to place Ferrier's discovery among Miller & Wheeler's chronologically. We follow the traditional order and put Ferrier's first, but there is good reason to doubt this.

For more information see *The History of the Theory of Numbers* by Leonard
Dickson [Dickson19].

In 1951 Miller and Wheeler began the electronic computing age by finding several primes:

k^{.}M_{127}+ 1 fork= 114, 124, 388, 408, 498, 696, 738, 774, 780, 934 and 978

as well as the new 79 digit record:

180(M_{127})^{2}+1 (here M_{127}= 2^{127}-1) [MW51].

This record was soon eclipsed by Raphael Robinson's discoveries of five new Mersennes the very next year using the SWAC (Standards Western Automatic Computer). This was the first program that Robinson had ever written, and it ran the very first time he tried it! Not only that, but his program found two new record primes that very day! He writes [Robinson54]:

The program was first tried on the SWAC on January 30, and two new primes were found that day [M_{521}, M_{607}], three other primes were found on June 25 [M_{1279}], October 7 [M_{2203}] and October 9 [M_{2281}].

It is interesting to note that in 1949 the topologist M. H. A Newman used the prototype Manchester electronic computer (with 1024 bits of storage) to make the first attempt to find Mersenne primes by computer. Perhaps because Alan Turing worked on this machine from 1948 to 1950, and improved the program by Newman, this first attempt at finding primes by (electronic) computers is sometimes attributed to him (e.g., [Robinson54] and [Ribenboim95, p93]). The excellent Alan Turing Internet Scrapbook has a picture of this machine.

We see the records of Miller, Wheeler, and Robinson as the first points on the following graph--note the vertical scale!

Progress over the next few years was as steady as the increase in speed of
computers. Riesel found M_{3217} using the Swedish machine BESK;
Hurwitz found M_{4253} and M_{4423} using an IBM 7090 (see
next paragraph); Gillies used the ILLIAC-2 to find M_{9689}, M_{9941} and
M_{11213}. Tuckerman found M_{19937} using an IBM360.

Surprisingly Hurwitz knew about M_{4423} seconds before M_{4253} (because
of the way the output was stacked). John Selfridge asked "Does a machine
result need to be observed by a human before it can be said to be 'discovered'?" To
which Hurwitz replied, "forgetting about whether the computer knew, what if
the computer operator who piled up the output looked?" In the table below
I decided that Hurwitz discovered the prime when he read the output, so M_{4253} was
never the largest known prime.

Number | Digits | Year | Machine | Prover |
---|---|---|---|---|

180(M_{127})^{2}+1 |
79 | 1951 | EDSAC1 | Miller & Wheeler |

M_{521} |
157 | 1952 | SWAC | Robinson (Jan 30) |

M_{607} |
183 | 1952 | SWAC | Robinson (Jan 30) |

M_{1279} |
386 | 1952 | SWAC | Robinson (June 25) |

M_{2203} |
664 | 1952 | SWAC | Robinson (Oct 7) |

M_{2281} |
687 | 1952 | SWAC | Robinson (Oct 9) |

M_{3217} |
969 | 1957 | BESK | Riesel |

M_{4423} |
1,332 | 1961 | IBM7090 | Hurwitz |

M_{9689} |
2,917 | 1963 | ILLIAC 2 | Gillies |

M_{9941} |
2,993 | 1963 | ILLIAC 2 | Gillies |

M_{11213} |
3,376 | 1963 | ILLIAC 2 | Gillies |

M_{19937} |
6,002 | 1971 | IBM360/91 | Tuckerman |

M_{21701} |
6,533 | 1978 | CDC Cyber 174 | Noll & Nickel |

M_{23209} |
6,987 | 1979 | CDC Cyber 174 | Noll |

M_{44497} |
13,395 | 1979 | Cray 1 | Nelson & Slowinski |

M_{86243} |
25,962 | 1982 | Cray 1 | Slowinski |

M_{132049} |
39,751 | 1983 | Cray X-MP | Slowinski |

M_{216091} |
65,050 | 1985 | Cray X-MP/24 | Slowinski |

391581*2^{216193}-1 |
65,087 | 1989 | Amdahl 1200 | Amdahl Six |

M_{756839} |
227,832 | 1992 | Cray-2 | Slowinski & Gage et al. (notes) |

M_{859433} |
258,716 | 1994 | Cray C90 | Slowinski & Gage |

M_{1257787} |
378,632 | 1996 | Cray T94 | Slowinski & Gage |

M_{1398269} |
420,921 | 1996 | Pentium (90 Mhz) | Armengaud, Woltman, et al. [GIMPS] |

M_{2976221} |
895,932 | 1997 | Pentium (100 Mhz) | Spence, Woltman, et al. [GIMPS] |

M_{3021377} |
909,526 | 1998 | Pentium (200 Mhz) | Clarkson, Woltman, Kurowski, et al. [GIMPS, PrimeNet] |

M_{6972593} |
2,098,960 | 1999 | Pentium (350 Mhz) | Hajratwala, Woltman, Kurowski, et al. [GIMPS, PrimeNet] |

M_{13466917} |
4,053,946 | 2001 | AMD T-Bird (800 Mhz) | Cameron, Woltman, Kurowski, et al. [GIMPS, PrimeNet] |

M_{20996011} |
6,320,430 | 2003 | Pentium (2 GHz) | Shafer, Woltman, Kurowski, et al. [GIMPS, PrimeNet] |

M_{24036583} |
7,235,733 | 2004 | Pentium 4 (2.4GHz) | Findley, Woltman, Kurowski, et al. [GIMPS, PrimeNet] |

M_{25964951} |
7,816,230 | 2005 | Pentium 4 (2.4GHz) | Nowak, Woltman, Kurowski, et al. [GIMPS, PrimeNet] |

M_{30402457} |
9,152,052 | 2005 | Pentium 4 (2GHz upgraded to 3GHz) | Cooper, Boone, Woltman, Kurowski, et al. [GIMPS, PrimeNet] |

M_{32582657} |
9,808,358 | 2006 | Pentium 4 (3 GHz) | Cooper, Boone, Woltman, Kurowski, et al. [GIMPS, PrimeNet] |

M_{43112609} |
12,978,189 | 2008 | Intel Core 2 Duo E6600 CPU (2.4 GHz) | E_Smith, Woltman, Kurowski, et al. [GIMPS, PrimeNet] |

M_{57885161} |
17,425,170 | 2013 | Cooper, Woltman, Kurowski, et al. [GIMPS, PrimeNet] | |

M_{74207281} |
22,338,618 | 2016 | Intel I7-4790 CPU | Cooper, Woltman, Kurowski, Blosser, et al. [GIMPS, PrimeNet] |

Curiously the prime M_{74207281} was detected by a machine months before a human noticed it--see the press releace for this prime.

All of the Mersenne records were found using the Lucas-Lehmer test and the other two were found using Proth's Theorem (or similar results). The Amdahl Six is J. Brown, C Noll, B Parady, G Smith, J Smith and S Zarantonello

**When will we have a one billion digit prime?** Good question! In the early days of the GIMPS search, my predictions were reasonable, but recently things have taken a turn (see the graph) that defies prediction using simple regressions and past history. My last prediction was way off!

I am getting out of the time prediction business. Future predictions should be based not only on heuristics such as found on the page Where is the Next Mersenne?, but should also track the usage data for projects like GIMPS. It is the current participants, not the past, which will find the next prime.

Another prime page by Chris K. Caldwell <