And the winning number is...

GIMPS finds a Multi-million digit prime!

One way to win a lottery is for several thousand folks to group together and buy tens of thousands of tickets, then there is a fair chance that one of the group will win. One June first, 1999, this strategy paid off for GIMPS: the Great Internet Mersenne Prime Search. On that day Nayan Hajratwala found a 2,098,960 digit Mersenne prime:

26972593-1.

This is GIMPS fourth Mersenne prime in as many years and the 38th known Mersenne prime (though it may not be the 38th in order of size since not all smaller exponents have been checked.)

So what has this to do with the lottery? Money for one thing. This makes Hajratwala eligible for the \$50,000 award that is offered by the Electronic Frontier Foundation (EFF). This time Hajratwala will pocket the whole \$50,000. Larger primes will earn up to \$250,000!

What is a Mersenne prime?

A prime is any integer greater than 1, which has only 1 and itself for positive divisors. (For example, the prime factors of 10 are 2 and 5.)  The first few primes are 2, 3, 5, 7 and 11. Mersenne primes are those which are a power of two, minus one. For example, the first few are 22-1=3, 23-1=7, 25-1=31, 27-1=127. These first few were known to the ancient Greeks several hundred years before Christ. See our page on Mersenne Numbers for more information, history and links (and be sure to check out the link between Mersennes and perfect numbers!).

How was it found?

Just how did Nayan Hajratwala (a PricewaterhouseCoopers employee in Plymouth, Michigan) find this prime? Not by himself! The key players are George Woltman, Scott Kurowski, and the 12,600 members of GIMPS and PrimeNet.

GIMPS was started by George Woltman to provide free software to find Mersenne primes and a database to coordinate the efforts of those involved. Scott Kurowski's company, Entropia.com, provided the distributed computing technology and services to make it trivial for anyone to join in the search via PrimeNet.

PrimeNet allows all the software to automatically contact the database and be assigned primes to work on and to record results--all without human intervention. In fact Hajratwala did not even know he had found this new prime on his home machine until PrimeNet mailed him because he, like most users, left it running in the background while the computer was idle.

"This has got to be the best email message I've ever read!" Nayan responded.
Nayan's home computer, a 350 MHz IBM Aptiva, used 111 days of idle time to find this prime, though it could have been done in three weeks if run full time on the same computer. David Willmore first verified the new Mersenne prime using a program written by Ernst Mayer (this took two weeks on a 500 MHz Alpha workstation).

How do you show a number this big is prime?

We can check small numbers for primality by just dividing by the lesser integers.  But to do that with a number the size of this new prime would take far longer than the universe has been in existence.  The key to winning a prize this size is a theorem developed by Lucas in the late 1870's and simplified by Lehmer, now called the Lucas-Lehmer Test.  Even as simple as this test is, it could not be done quickly without using very clever programs to multiply the numbers. In 1968 Strassen discovered how to multiply quickly using Fast Fourier Transforms. He and Schönhage refined and published the method in 1971. GIMPS now uses an improved version of their algorithm developed by the long time Mersenne searcher Richard Crandall [see CF94].

Nayan Hajratwala, George Woltman, and Scott Kurowski share the credit and glory for this prime with all of the others involved in this effort!   There are still infinitely many more giants left to slay, so why not surf over to Woltman's GIMPS site and join the search for the next record prime?  Perhaps you too can earn thousands of dollars with your computer's spare time!