VACETS Logo

VACETS Regular Technical Column

The VACETS Technical Column is contributed by various members , especially those of the VACETS Technical Affairs Committe. Articles are posted regulary on vacets@peak.org forum. Please send questions, comments and suggestions to vacets-ta@vacets.org


September 10, 1996

Largest Known Prime Number Discovered


About 2 years ago, Andrew Wiles, a researcher at Princeton, claims to have proved the Fermat's Last Theorem (FLT) and later a large gap was found in the proof. (The gap was filled later at the end of 1994.) At that time, we, the VACETSERS, had debated on proving the FLT using numerical methods (i.e., using computer to crank out the solutions to the famous theorem). One of the first steps in numerical method is to find the prime numbers, and from that, a "fastest prime number generator" war was waged among us the VACETSERS. The result of that "war" was that we were able to reduce the time from tens of seconds to find all the primes below 1 million to less than 1 second to find all the primes below 10 million. It was an improvement of more than 100. It was a fun war. (Actually, for me, anything involved with numbers, especially prime numbers, is fun.)

Shortly after that "fastest prime number generator" war, Thomas R. Nicely, Professor of Mathematics at Lynchburg College, Virginia, computed the sums of the reciprocals of the twin primes (such as 11 and 13), triplets (such as 11, 13, and 17), and quadruplets (such as 11, 13, 17, and 19) up to a very large upper bound (about 10 trillion). He discovered during the summer and fall of 1994 that one of the reciprocals had been calculated incorrectly by a Pentium computer, although a 486 system gave the correct answer; this led to the publicization of the hardware divide flaw in the Pentium floating point unit.

Last week, 9/3/96, an other prime number news surfaced: The largest known prime is found by a SGI/Cray supercomputer in the process of quality assurance testing on its systems. The new prime number, 2^1257787-1 (which denotes 2 multiplied by itself 1,257,787 times minus one) is the 34th Mersenne prime, discovered by David Slowinski and Paul Gage. It took about 6 hours on a Cray T94 supercomputer to check this number. For a 90-MHz Pentium, it would take about 60 hours. The previous largest known Mersenne prime, 2^859433-1, was also discovered by Slowinski and Gage in 1994.

Before getting too far with the new discovery, let's review some basic of prime numbers.

What is a prime number? A prime number is a positive integer that can be divided only by itself and the number 1. The first few prime numbers are 2, 3, 5, 7, 11...

What is a Mersenne prime? A Mersenne prime is a prime number that has the form 2^p-1 where p is also a prime. Ex: 3=2^2-1 and 7=2^3-1 are the first 2 Mersenne primes.

History: Many early mathematicians felt that the numbers of the form 2^p-1 were prime for all primes p. But, in 1536, Hudalricus Regius showed that 2^11-1 = 2047 was not prime (it is 23*89). This meant that 2^p-1 might or maight not be prime. By 1588 Pietro Cataldi had correctly verified that 2^17-1 and 2^19-1 were both prime.

In 1644, Father Marin Mersenne, a French monk, stated that the numbers 2^p-1 were prime for p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 and 257. Mersenne's conjecture, even though later proved to be incorrect, got his name attached to these numbers.

It was obvious to Mersenne's peers that he could not have tested all of these numbers, but they could not test them either.

Cataldi's prime (p=19) stood to be the largest known prime for about 2 centuries until Leonhard Euler in 1772 proved that 2^31-1 is prime. (Through out the history, Mersenne primes were almost always the largest known primes.) This established the record for another century until 1876, when Edouard Lucas showed that 2^127-1 (which is a 39 digit number) is prime, and that took the record as far as the age of the electronic computer. Seven years later I.M. Pervushin showed 2^61-1 was prime, so Mersenne had missed this one. In the early 1900's R.E. Powers showed that Mersenne had also missed the primes 2^89-1 and 2^107-1. Finally, by 1947, Mersenne's range, p < 258, had been completely checked and it was determined that the correct list is: p = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107 and 127.

In 1952 the Mersenne numbers p = 521, 607, 1279, 2203, and 2281 were proved to be prime by Robinson using an early computer and the electronic age had begun.

By 1996 a total of 34 Mersenne primes have been found. The largest and most recent is p = 1,257,787 which has 378,632 decimal digits.

The table of known Mersenne primes as of September 3, 1996 is shown below.

   n         p    Year    Discoverer
  --    ------    ----    ----------------------
   1         2      -     -
   2         3      -     -
   3         5      -     -
   4         7      -     -
   5        13    1461    Anonymous
   6        17    1588    P. A. Cataldi
   7        19    1588    P. A. Cataldi
   8        31    1750    L. Euler
   9        61    1883    I. M. Pervushin
  10        89    1911    R. E. Powers
  11       107    1914    R. E. Powers
  12       127    1876    E. Lucas
  13       521    1952    R. M. Robinson
  14       607    1952    R. M. Robinson
  15      1279    1952    R. M. Robinson
  16      2203    1952    R. M. Robinson
  17      2281    1952    R. M. Robinson
  18      3217    1957    H. Riesel
  19      4253    1961    A. Hurwitz & J. L. Selfridge
  20      4423    1961    A. Hurwitz & J. L. Selfridge
  21      9689    1963    D. B. Gillies
  22      9941    1963    D. B. Gillies
  23     11213    1963    D. B. Gillies
  24     19937    1971    B. Tuckerman
  25     21701    1978    L. C. Noll & L. Nickel
  26     23209    1979    L. C. Noll
  27     44497    1979    D. Slowinski & H. Nelson
  28     86243    1982    D. Slowinski
  29    110503    1988    W. N. Colquitt & L. Welsch, Jr.
  30    132049    1983    D. Slowinski
  31    216091    1985    D. Slowinski
  32?   756839    1992    D. Slowinski & P. Gage
  33?   859433    1994    D. Slowinski & P. Gage
  34?  1257787    1996    D. Slowinski & P. Gage

It is not known if these last three primes are the 32nd through 34th Mersenne primes as the region between them and the previous primes has not been completely tested. Notice that the 29th Mersenne was found while scanning the region between two primes found five years earlier.

The way to determine if 2^p - 1 is prime, given that p is prime, is to use the Lucas-Lehmer test:

u := 4; for i := 3 to p do u := (u^2 - 2) mod (2^p - 1); if u == 0 then 2^p - 1 is prime; else 2^p - 1 is composite;

The theory for this test was initiated by Lucas in the late 1870's and then made into this simple test about 1930 by Lehmer.

Note that, with the discovery of the new prime number, a new perfect number can also be generated. A perfect number is equal to the sum of its factors. For example, 6 is perfect because its factors 1, 2 and 3, when added together, equal 6; the next is 28 = 1+2+4+7+14. Mathematicians don't know how many perfect numbers exist. They do know, however, that all even perfect numbers have a direct relationship to Mersenne primes, P = 2^(p-1)*(2^p-1) where 2^p-1 is a Mersenne prime. The new Mersenne prime has 378,632 digits and the new even perfect number generated with the new Mersenne prime is the 34th known perfect number and has 757,263 digits. It is not known whether or not there is an odd perfect number, but if there is one then it is a perfect square times an odd power of a single prime; it is divisible by at least eight primes and has at least 29 prime factors; and it has at least 300 decimal digits.

Finding the largest prime numbers does not have to be exclusive right of high-powered supercomputers. A Florida-based programmer has organized a hunt for the search for Mersenne Primes using PC. George Woltman, the search organizer, wanted to take advantage of the fact that PC central processors waste most of their computing power because they run on idle much of the time. So Woltman wrote a program that uses PC, when it's not doing anything else, to help find Mersenne primes. Then he spread the word on the Internet, in part by setting up a special World Wide Web site, and asked for help. About 400 volunteers from around the world have signed up, and Woltman is looking for more. If you'd like to help, you can check out the web at

http://ourworld.compuserve.com/homepages/justforfun/prime.htm.

Below is the list of some of the web sites containing the related information on the latest Mersenne prime number.

HAPPY NUMBER CRUNCHING, EVERYONE.



    Vo Ta Duc

    ducvo@Lanl.GOV

    For discussion on this column, join vacets-tech@teleport.com


    Copyright © 1996 by VACETS and Vo Ta Duc

Other Articles

How high can you suck?

Asynchronous Transfer Mode (ATM) - An analogy

The UNIX Run-time Environment

National Information Infrastructures In Asia Pacific: Visions, Reality and Research Inquiry


Other Links

VACETS Home Page

VACETS Electronic Newsletter

VACETS FTP Site