The largest known primes are Mersenne primes, in part because the Lucas-Lehmer algorithm makes it more efficient to test Mersenne numbers for primality than to test arbitrary numbers. These numbers have the form 2n − 1.
The Great Internet Mersenne Prime Search (GIMPS) announced today that they have tested whether 2n – 1 is prime for all values of n less than 100,000,000 [1]. More specifically, they’ve tested each exponent at least once, though they’d like to test each exponent twice before giving up on it.
If we assume all of their initial calculations are correct, we can say, for example, that 282,589,933 − 1 is the 51st Mersenne prime. Before we had to say that it was the 51st known Mersenne prime because there could be a smaller, undiscovered Mersenne prime, in which case 282,589,933 − 1 might be the 52nd Mersenne prime. Mersenne primes have not always been discovered in order. For example, the 29th Mersenne prime was discovered after the 30th and 31st such numbers.
So for now, again assuming all the GIMPS calculations have been correct, we know all Mersenne primes less than 2100,000,000, and there are 51 of them.
Related posts
[1] There’s no need to test every value of n. We know that if 2n − 1 is prime, then n is prime. So we only need to check prime values of n.
Why the need to check multiple times?
@Sam: To reduce the chances of a false negative due to an error, such as a cosmic ray bit flip.
If the software were factoring numbers to prove that they are composite, it would be quick to verify the results by multiplying the factors. But one reason why finding enormous Mersenne primes is practical is that you can show that a Mersenne number is composite without finding its factors. The downside, however, is that the only way to verify the result is to repeat the calculation, and these calculations take a lot of time.
Within [1], the exponent p should be n — as in “if 2^(n) – 1 is prime [for some integer n], then n is prime.” Apologies for being a stickler, but I figured to mention it since it is a well-known Mathematical statement while this is a good/interesting post at the same time.