Great Internet Mersenne Prime Search

page 1 | 2

Fig. 1: French mathematician Marin Mersenne discovered special types of prime numbers. (Courtesy of Dr. John O'Connor )

The Great Internet Mersenne Prime Search, also known as GIMPS, is a prime example of distributed computing at work — no pun intended. The goal of the GIMPS project is — as the name states — to find new Mersenne prime numbers. Mersenne primes are numbers that can be found using the equation 2^P - 1. When the resulting number is prime, P is a Mersenne prime. For example, 23 - 1 = 7. Seven is a prime number; thus, three is a Mersenne prime. There have been only 38 Mersenne prime numbers found, and the GIMPS search is focusing on the large primes — numbers so huge that it could take your computer up to a year to crunch one exponent.

The Mersenne primes aren't just pretty numbers, though: they do have many applications. Most common uses for these primes are for forming algorithms, and, interestingly enough, testing computer hardware. The most notable instance occurred when Intel used software routines from the GIMPS project to test the Pentium II and Pentium Pro chips before releasing the chips. The reason that these primes are used to test hardware is, according to mathematics Professor Chris Caldwell, "they are relatively short, give an easily checked answer...They can easily be run in the background while other 'more important' tasks run, and they are usually easy to stop and restart." (Caldwell: "Why do people...")

The Mersenne prime search was formed in 1996, and — ever since the project launched — a new world-record Mersenne prime has been discovered every year. When the project began, there were only 40 people and a little over 50 computers using their spare CPU cycles; the project has since grown to thousands of users and computers. The software has also changed quite a bit from GIMPS's beginnings; at first, there were many errors that were made in checking for primes, and all discovered Mersenne primes had to be double-checked to ensure their validity.

Anyone with an Intel-compatible computer can participate in this distributed computing project. However, depending on the computer's speed, a person may have greater or less odds of finding a prime. The project uses a test called the Lucas-Lehmer test, which is simply a proof of the 2^P - 1 equation; the computer tests large exponents (the P) by plugging them into the equation. The GIMPS server, Primenet, assigns fast computers, like Pentium II 300 mHz, "first-time primality tests." ("How GIMPS works") This means those computers check previously unchecked ranges of numbers using the Lucas-Lehmer test, and have the greatest chance of finding a new Mersenne prime. The workload is heavy; it may take up to a month to process the exponents. Pentium 90 mHz and faster computers are assigned to check the work done in the primality tests. These computers have a very small chance of finding a prime — their only chance is if the original test didn't catch the number. Slower computers do factoring work, which assists the primality tests since some exponents are eliminated, and the process becomes faster.

continued...

©2000 Team DC (Thinkquest Team C007645). Hosted by ThinkQuest.