And the winning number is...
By Chris Caldwell
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?
![[Pictures of the Main Players]](pictures.gif)
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.
For more information on PrimeNet and GIMPS see the official
press release.
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!
"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?
Links to more information
For
more information click on one of the following: