A prime number is an integer greater than 1 whose only positive divisors are 1 and the number itself. Thus, the numbers 2, 3, 5, 7, 11, 13, 17, ... are prime. In Vignette 2, you saw an elementary proof that there are infinitely many prime numbers. It was also pointed out that there is no formula that will generate all primes in sequence. Because of this fact, both professional and amateur mathematicians have for years attempted to determine larger and larger prime numbers.
Mersenne Primes
Since no formula can generate all prime numbers, attention has turned to looking for prime numbers that have a specific form. One such form that has been explored a great deal is that of Mersenne primes, named for Marin Mersenne, a French monk who began the study of these numbers in the early 1600's. A Mersenne prime is a prime number of the form 2 p - 1, where p is a prime. For instance, 2 2 - 1= 3 is prime, 2 3 - 1 = 7 is prime, 2 5 - 1 = 31 is prime, and so on. Not all such numbers are prime, however; for example, 2 11 - 1 = 2047 = 23 . 89 is not prime.
One reason for the attention to primes of this type is that it is relatively easy to test a number of the form 2 p - 1 to see if it is prime. One simple criterion is that the factors of a number of the form 2 p - 1 must have the form 2kp + 1, and must also have the form 8n + 1 or 8n -1, where k and n are integers. It is therefore easy to generate a crude list of possible factors, and then to test the number 2 p - 1 to see if any of these actually are factors. Over the years, improvements have been made on the test of primality for numbers of the form 2 p - 1. Today, the efforts to test numbers for primality have, naturally enough, centered around the use of computers.
The Largest Known Primes
As of this writing (July, 2000), the largest known prime is the Mersenne prime 26,972,593 - 1, a number with over 2 million digits. This is only the 38th in the sequence of Mersenne primes. This prize-winning prime number was discovered using GIMPS (the Great Internet Mersenne Prime Search). GIMPS, which was developed in 1996, is a cooperative venture in which people volunteer the background time on their personal computers to search for prime numbers. A central server on the internet coordinates the efforts of those participating, and records the results. Searching for primes is serious business. The Electronic Frontier Foundation has offered a $100,000 prize to the first person or group to find a prime number with at least ten million digits! The current record-holding Mersenne prime garnered a $50,000 prize from the EFF. Current estimates are that the $100,000 prize will be claimed by late 2001, and that a billion-digit prime will be discovered by 2006.
Apart from the fact that larger Mersenne primes may be discovered in the future, there are a number of unsolved questions concerning this type of number. For instance, it is not known whether there are infinitely many Mersenne primes. Most mathematicians think that the answer is "yes," but it has not yet been proven!
Why So Much Interest in Primes?
You might wonder whether the search for large primes is of any value. Apart from the adventurous spirit of exploration, there actually are uses for large prime numbers. One of the most important applications is to the field of cryptography -- the encoding and decoding of messages. National security often relies on having a secure method of encoding and deciphering messages; yet the existence of high-speed computers have rendered all but the most sophisticated coding schemes insecure. One commonly used method of message coding is the RSA scheme, named for its creators, Ron Rivest, Adi Shamir, and Len Adleman. The RSA scheme relies on the fact that it is easy to multiply two prime numbers, yet hard to factor their product -- especially if the prime numbers are large. Consequently, knowledge of large prime numbers can lead to coding schemes that are difficult to break.
Further Exploration