The Largest Known prime by Year: A Brief History

By Chris Caldwell

The largest known prime today is the 24,862,048 digit Mersenne prime 2^82589933-1 found in December 2018, 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.

Contents

1. Before Electronic Computers
   • Table of the Record Prime by Year
2. The Age of Electronic Computers
   • Graph of the Record Prime by Year
   • Table of the Record Prime by Year
3. Epilogue: No more predictions
   • The First Billion Digit Prime

Part One: Before Computers

For information on 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¹⁷-1 = 131071 and 2¹⁹-1 = 524287 are both prime [Cataldi1603].

But Cataldi also had incorrectly stated 2ⁿ-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¹⁹-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¹³-1 (before 1458, Codice Palatino 573) and 131071=2¹⁷-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 2kp+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³¹-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³¹-1 prime by showing all prime divisors of 2³¹-1 must have one of the two forms 248n+1 and 248n+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³¹-1 a prime as early as 1732, but he did so along with 2⁴¹-1 and 2⁴⁷-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⁶⁴+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⁵⁹-1 (namely (2⁵⁹-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.)

Table 1. Records before Electronic Computers

Number	Digits	Year	Prover	Method
217-1	6	1588	Cataldi	trial division
219-1	6	1588	Cataldi	trial division
231-1	10	1772	Euler	trial division++
(259-1)/179951	13	1867	Landry	trial division++
2127-1	39	1876	Lucas	Lucas sequences
(2148+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¹²⁷-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¹⁴⁸+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].

Part Two: Electronic Computers

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

as well as the new 79 digit record:

180(M₁₂₇)²+1 (here M₁₂₇ = 2¹²⁷-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₅₂₁, M₆₀₇], three other primes were found on June 25 [M₁₂₇₉], October 7 [M₂₂₀₃] and October 9 [M₂₂₈₁].

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₃₂₁₇ using the Swedish machine BESK; Hurwitz found M₄₂₅₃ and M₄₄₂₃ using an IBM 7090 (see next paragraph); Gillies used the ILLIAC-2 to find M₉₆₈₉, M₉₉₄₁ and M₁₁₂₁₃. Tuckerman found M₁₉₉₃₇ using an IBM360.

Surprisingly Hurwitz knew about M₄₄₂₃ seconds before M₄₂₅₃ (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₄₂₅₃ was never the largest known prime.

Table 2. Records by Electronic Computer

Number	Digits	Year	Machine	Prover
180(M127)2+1	79	1951	EDSAC1	Miller & Wheeler
M521	157	1952	SWAC	Robinson (Jan 30)
M607	183	1952	SWAC	Robinson (Jan 30)
M1279	386	1952	SWAC	Robinson (June 25)
M2203	664	1952	SWAC	Robinson (Oct 7)
M2281	687	1952	SWAC	Robinson (Oct 9)
M3217	969	1957	BESK	Riesel
M4423	1,332	1961	IBM7090	Hurwitz
M9689	2,917	1963	ILLIAC 2	Gillies
M9941	2,993	1963	ILLIAC 2	Gillies
M11213	3,376	1963	ILLIAC 2	Gillies
M19937	6,002	1971	IBM360/91	Tuckerman
M21701	6,533	1978	CDC Cyber 174	Noll & Nickel
M23209	6,987	1979	CDC Cyber 174	Noll
M44497	13,395	1979	Cray 1	Nelson & Slowinski
M86243	25,962	1982	Cray 1	Slowinski
M132049	39,751	1983	Cray X-MP	Slowinski
M216091	65,050	1985	Cray X-MP/24	Slowinski
391581 ·2216193-1	65,087	1989	Amdahl 1200	Amdahl Six
M756839	227,832	1992	Cray-2	Slowinski & Gageet al. (notes)
M859433	258,716	1994	Cray C90	Slowinski & Gage
M1257787	378,632	1996	Cray T94	Slowinski & Gage
M1398269	420,921	1996	Pentium (90 Mhz)	Armengaud, Woltman, et al. [GIMPS]
M2976221	895,932	1997	Pentium (100 Mhz)	Spence, Woltman, et al. [GIMPS]
M3021377	909,526	1998	Pentium (200 Mhz)	Clarkson, Woltman, Kurowski, et al. [GIMPS, PrimeNet]
M6972593	2,098,960	1999	Pentium (350 Mhz)	Hajratwala, Woltman, Kurowski, et al. [GIMPS, PrimeNet]
M13466917	4,053,946	2001	AMD T-Bird (800 Mhz)	Cameron, Woltman, Kurowski, et al. [GIMPS, PrimeNet]
M20996011	6,320,430	2003	Pentium (2 GHz)	Shafer, Woltman, Kurowski, et al. [GIMPS, PrimeNet]
M24036583	7,235,733	2004	Pentium 4 (2.4GHz)	Findley, Woltman, Kurowski, et al. [GIMPS, PrimeNet]
M25964951	7,816,230	2005	Pentium 4 (2.4GHz)	Nowak, Woltman, Kurowski, et al. [GIMPS, PrimeNet]
M30402457	9,152,052	2005	Pentium 4 (2GHz upgraded to 3GHz)	Cooper, Boone, Woltman, Kurowski, et al. [GIMPS, PrimeNet]
M32582657	9,808,358	2006	Pentium 4 (3 GHz)	Cooper, Boone, Woltman, Kurowski, et al. [GIMPS, PrimeNet]
M43112609	12,978,189	2008	Intel Core 2 Duo E6600 CPU (2.4 GHz)	E_Smith, Woltman, Kurowski, et al. [GIMPS, PrimeNet]
M57885161	17,425,170	2013	Intel Core2 Duo E8400 (3 GHz)	Cooper, Woltman, Kurowski, et al. [GIMPS, PrimeNet]
M74207281	22,338,618	2016	Intel I7-4790 CPU	Cooper, Woltman, Kurowski, Blosser, et al. [GIMPS, PrimeNet]
M77232917	23,249,425	2018	Intel i5-6600 CPU	Pace, Woltman, Kurowski, Blosser, et al. [GIMPS, PrimeNet]
M82589933	24,862,048	2018	Intel i5-4590T CPU	Laroche, Woltman, Blosser, et al. [GIMPS, PrimeNet]

Curiously the prime M_74207281 was detected by a machine months before a human noticed it--see the press release 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.

Epilogue: No Predictions

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. So we will end with a linear graph and a gratuitous cubic below. Useful 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.