Searching for Mersenne Primes
People May Participate to Find the Next Very Large Prime Number
There are only 44 known Mersenne primes. GIMPS provides free software for people to search for the next Mersenne Prime and may claim award prize money if successful.
A previous article focused on basic searching for prime numbers using a sieve of Eratosthenes. These prime numbers are infinite in extent as is suggested by Euclid’s Second Theorem, hence the prime search technique could be applied ad infinitum. However, numbers soon get so large that they become difficult to handle. It was quite a long time after Euclid that mathematicians could explicitly point to some very large primes.
Mersenne Primes
A French priest, Marin Mersenne (1588 – 1648) was intrigued by numbers M of the form:
- M = 2^p – 1, where the hat symbol (^) refers to power of the number.
That is, numbers are one less than a power of 2. Today these numbers are called Mersenne numbers in his honor. The following are some observations about the relationship between the exponent p and the Mersenne number.
- M numbers are obviously odd numbers
- If p is composite, then M is also composite (composite here means factored)
- If p is prime, then M is only sometimes prime
There are a total of 44 known Mersenne Primes and others are being searched for every day. The first few Marsenne primes are:
3, 7, 31, 127, 8191, 131071, 524287, 2147483647, 2305843009213693951, …
It can be seen that the number of digits starts off small for the first few terms but then grows very, very large, to the point that results have to be quoted in number of digits, and these data are saved in a text file. For example, the largest known prime is M44 and has 808358 digits. The text file holding the data is 9.827 Mb!
Testing for Primes
The first few prime numbers are 2, 3, 5, 7, 11, ... Smaller primes can be checked by dividing by the lesser numbers. But to do that for the size of a large Mersenne prime it would take longer than the universe has been in existence. The key is to use a theorem developed by Lucas, an algorithm now called the Lucas-Lehmer Test, and a fast search transform.
The Great Internet Mersenne Prime Search
The Great Internet Mersenne Prime Search (GIMPS) is a group of people interested in finding the next Mersenne prime using the computer power of people’s PCs around the world. Once their software is downloaded from the website and installed, anybody can participate in this prime search. The Electronic Frontier Foundation is offering a $100,000 award to the first person or group to discover a ten million digit prime number. If users find such a prime with the software provided, GIMPS will claim the award and distribute the award according to set rules.
Other articles by the Author
Basic Searching for Prime Numbers
