[go: up one dir, main page]

Giant Slaying Refined: 23021377-1

By Chris Caldwell

[Pictures of the three]

GIMPS (the Great Internet Mersenne Prime Search) now has a third Mersenne prime to its credit: the 909,526 digit number 23021377-1.

Just how did Roland Clarkson (a 19 year-old student at California State University Dominguez Hills) find this giant?  About two years ago GIMPS founder George Woltman wrote a very efficient program for finding Mersenne primes and established an Internet database to facilitate this search (combining the work of many previous searchers). Recently Scott Kurowski (and others) developed PrimeNet--allowing George's program to talk directly to the database over the Internet without human intervention.  Now, with approximately four thousand individuals using these programs and consuming approximately a decade of CPU time each day, a new prime seemed virtually assured; but no-one knew when it might be found. (We say "virtually assured," because though it is conjectured that there are infinitely many Mersenne primes, this has not yet been proven.)

On January 27th, 1998, all this work came together--after many days of computer time, Clarkson found this record Mersenne prime on his home computer! When the PrimeNet server chose this exponent for him to test, Clarkson did not want to test it. "I never would have imagined two Mersenne primes would be so close together!" he said. He went ahead anyway and found the smallest gap yet (in terms of percentage) between any two Mersenne primes. The actual test took about 46 days while running part-time on a 200-MHz Pentium computer. (It would have taken about a week if the computer was working full-time.)

David Slowinski of Cray Research finished verifying the primality on January 30th. So it is now confirmed as the largest known prime, the 37th known Mersenne Prime, and gives rise to the 37th known perfect number: 23021376.(23021377-1), which has 1,819,050 digits. Soon we expect to see a million (plus) digit megaprime! Why not join GIMPS and try to find it?

How do you show a number that large is prime?

A prime is an 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.  We can check small numbers 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 slaying a giant 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]. 

Is that it, just get a fast program?

Even a fast program is not enough, what GIMPS does is coordinate the efforts of over four thousand computer users--by (1) providing free software, (2) supplying a database of known results, and (3) allowing individuals to check out regions to test (either manually, or better, using a version that automatically contacts the database via Kurowski's PrimeNet Server).

Roland Clarkson, George Woltman, and Scott Kurowski share the credit and glory 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? 

For more information click on one of the following:

 
Printed from the PrimePages <t5k.org> © Reginald McLean.