Mersenne Megaprime

This time, it's a great leap forward.

On June 1, a participant in the Great Internet Mersenne Prime Search (GIMPS) discovered the first known prime number with at least 2 million decimal digits--more than twice as many as the previous record holder.

The discoverer was Nayan Hajratwala, a consultant at PricewaterhouseCoopers in Plymouth, Mich. Using a Pentium-based personal computer and software written by George Woltman of Orlando, Fla., he identified 2^6,972,593 - 1 as a prime number, evenly divisible only by itself and 1. Its 2,098,960 decimal digits qualify Hajratwala for a $50,000 prize offered by the Electronic Frontier Foundation (EFF) in Palo Alto, Calif., for the first individual or group who discovers a prime number with at least 1 million digits.

The newly discovered number is the 38th known Mersenne prime, named for the French cleric and mathematician Marin Mersenne (1588-1648). Expressed in the form 2^p- 1, where the exponent p is itself prime, Mersenne numbers have characteristics that make it relatively easy to determine whether a candidate is prime. For example, written out in binary form, a Mersenne number consists of an unbroken string of 1s--6,972,593 of them in the case of the record holder.

The smallest Mersenne prime is 3 (2² - 1), or in binary digits, 11. After that comes 7 (2³ - 1), or 111, then 31 (2⁵ - 1), or 11111.

With an exponent of 6,972,593, the new champion holds the distinction of being the largest Mersenne prime identified so far. However, because no one has yet checked all Mersenne numbers having smaller exponents, mathematicians can't be sure that no Mersenne primes lurk in the vast expanse between the record holder and the second-place Mersenne prime, which has an exponent of 3,021,377.

Searching for such large primes has entailed a massive group effort, orchestrated by Woltman, who started GIMPS (see Another Record Prime, Dec. 16, 1996), and facilitated by networking software developed by Scott Kurowski of Entropia.com in San Jose, Calif. Kurowski's PrimeNet server automatically distributes work to and gathers results from thousands of copies of Woltman's program residing on more than 21,500 computers throughout the world. The program runs whenever its host computer is otherwise idle, during the night or even between mouse clicks.

Woltman's software, in turn, relies on a computational algorithm invented by Richard E. Crandall of Reed College and Perfectly Scientific, Inc. in Portland, Ore. That algorithm, called the irrational base discrete weighted transform, speeds up certain large multiplication operations. Crandall's company has produced a poster featuring (in fine print) all 2,098,960 decimal digits of the current record holder.

Anyone can join the great prime hunt. All it takes is a sufficiently powerful personal computer with idle time on its chips. Check out http://www.mersenne.org/prime.htm for details.

Besides the glory of holding a world record (at least for a while), there is now also a financial incentive. The recently instituted EFF prize for finding a prime number with at least 10 million decimal digits is $100,000. The foundation's hope is that the prize will spur the technology of cooperative computing and encourage Internet users worldwide to join together in solving scientific problems involving massive computation.

"Using current algorithms, this is more than 125 times as difficult as finding a 2-million-digit prime," Kurowski says. "GIMPS and Entropia.com are gearing up for this challenge now."

"It's like playing the lottery," comments Joe P. Buhler, deputy director of the Mathematical Sciences Research institute in Berkeley, Calif. "If you're really lucky, you'll come up with a winner."

References:

Bennett, R. 1999. Prime-number coup lets consultant pocket another number: $50,000. Oregonian (July 7).

______. 1999. 2-million-digit number is a prime prize. Oregonian (June 26).

Chui, G. 1999. New prime is discovered via Internet. San Jose Mercury News (July 6).

Crandall, R.E. 1997. The challenge of large numbers. Scientific American (February):74.

Peterson, I. 1998. Calculating a record prime. Science News 153(Feb. 21):127.

______. 1997. Lucky choice turns up world-record prime. Science News 152(Sept. 13):164.

Additional information about the Great Internet Mersenne Prime Search and the discovery of the 38th Mersenne prime is available at http://www.mersenne.org/prime.htm.

Richard Crandall's Web site (Perfectly Scientific, Inc.) at http://www.perfsci.com offers for sale a wall poster displaying the 2,098,960 decimal digits of the 38th known Mersenne prime.

Learn more about Mersenne primes and the new record at http://www.utm.edu/research/primes/mersenne.shtml.

Details about the Electronic Frontier Foundation's cooperative computing awards can be found at http://www.eff.org/coop-awards.

Comments are welcome. Please send messages to Ivars Peterson at ipeterson@maa.org.