The Largest Known Prime by Year A Brief History Chris Caldwell Note: If you do not see superscripts and subscripts in this sentence, then click here for a version of this page without super/subscripts. As of 27 January 1998 the largest known prime is the 909526 digit Mersenne prime 23021377-1, but how big have the "largest known primes" been historically? When might we see the first million digit megaprime? And historically, how have these primes been found? We will briefly discuss each of these questions below. [Image] Contents 1. Before Electronic Computers o Table of the Record Prime by Year 2. The Age of Electronic Computers o Graph of the Record Prime by Year o Table of the Record Prime by Year 3. Epilogue: Predictions o The First Million Digit Prime ------------------------------------------------------------------------ Primes: [ Home || Largest | Proving | How Many? | Mersenne | Glossary | Guestbook ] ------------------------------------------------------------------------ [up] Part One: Before Electronic Computers Many early writers felt (incorrectly) that if p was prime, then so was Mp = 2p-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 asMersenne, Leibniz, and Euler. So we give credit to our first record holder with some doubt: by 1588 Pietro Cataldi had correctly verified that 217-1 = 131071 and 219-1 = 524287 are both prime. But Cataldi also had incorrectly stated 2n-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 219-1 is prime (its square root is approximately 724) but not large enough to handle these four larger numbers! In 1640 Fermat showed that if p is an odd prime, then all prime divisors of 2p-1 have the form 2kp+1. He then quickly showed Cataldi was wrong about 23 (which has a factor with k=1) and 37 (factor at k=6). 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 all three of these factors found to show Cataldi's errors could be found in Cataldi's own tables! 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 231-1 = 2147483647 is prime. The actual date must be between October 1753 when Euler sent a letter to Goldbach stating he was uncertain about this number (even though he had earlier listed it as prime) and 1772 when a letter was published from Euler to Bernoulli stating he proved 231-1 prime by showing all prime divisors of 231-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 231-1 a prime as early as 1732, but he did so along with 241-1 and 247-1 both of which were composite.) By 1867 Landry had found a larger prime, still by trial division, as a factor of 259-1 (namely (259-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. 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 determinine 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 2127-1 = 170141183460469231731687303715884105727 was prime. "This remained the largest known prime until 1951" [H&W79 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 (2148+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. For more information see The History of the Theory of Numbers by Leonard Dickson [Dickson19]. [up] Part Two: The Age of Electronic Computers In 1951 Miller and Wheeler began the electronic computing age by finding several primes: k.M127 + 1 for k = 114, 124, 388, 408, 498, 696, 738, 744, 780, 934 and 978 as well as the new 79 digit record 180(M127)2+1 (here M127 = 2127-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, it ran the very first time he tried it and found two new primes that day! He writes [Robinson54]: The program was first tried on the SWAC on January 30, and two new primes were found that day [M521, M607], three other primes were found on June 25 [M1279], October 7 [M2203] and October 9 [M2281]. 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! [A surprisingly linear graph of log(digits) versesyear] Progress over the next few years was as steady as the increase in speed of computers. Riesel found M3217 using the Swedish machine BESK; Hurwitz found M4253 and M4423 using an IBM 7090 (see next paragraph); Gillies used the ILLIAC-2 to find M9689, M9941 and M11213. Tuckerman found M19937 using an IBM360. Surprisingly Hurwitz knew about M4423 seconds before M4253 (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 M4253 was never the largest known prime. [What is adiscoverer?] 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 1332 1961 IBM7090 Hurwitz M9689 2917 1963 ILLIAC 2 Gillies M9941 2993 1963 ILLIAC 2 Gillies M11213 3376 1963 ILLIAC 2 Gillies M19937 6002 1971 IBM360/91 Tuckerman M21701 6533 1978 Cyber 174 Noll & Nickel M23209 6987 1979 Cyber 174 Noll M44497 13395 1979 Cray 1 Nelson & Slowinski M86243 25962 1982 Cray 1 Slowinski M132049 39751 1983 Cray X-MP Slowinski M216091 65050 1985 Cray X-MP Slowinski 391581*2216193-1 65087 1989 Amdahl 1200 Amdahl Six M756839 227832 1992 Cray-2 Slowinski & Gage M859433 258716 1994 Cray C90 Slowinski & Gage M1257787 378632 1996 Cray T94 Slowinski & Gage M1398269 420921 1996 Pentium (90 Armengaud, Woltman, et. Mhz) al. [GIMPS] M2976221 895932 1997 Pentium (100 Spence, Woltman, et. al. Mhz) [GIMPS] Clarkson, Woltman, M3021377 909526 1998 Pentium (200 Kurowski, et. al. [GIMPS, Mhz) PrimeNet] 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 [up] Epilogue: Predictions When will we have a one million digit prime? Before this last two primes were found I had looked at the regression line above (R2=0.95) which suggests the first mega-prime might be found late June, 2002. Now, ignoring the data before 1979, we get the (seemingly) more reasonable estimate of January, 1999 (R2=0.97). But it could easily be tomorrow if one of the GIMPS members gets lucky--maybe it will be you! Note the latter trend line suggests we might see a billion digit prime by the end of the first quarter of 2009! ------------------------------------------------------------------------ Page by Chris K. Caldwell