New Prime Number Discovered

Mathematicians at UCLA have discovered a 13 million-digit prime number, a long-sought milestone that makes them eligible for a $100,000 prize given out by the EFF.

The group found the 46th known Mersenne prime last month on a network of 75 computers running Windows XP. The number was then verified by a different computer system.

What is the importance of finding a new prime number?

Finding new Mersenne primes is not likely to be of any immediate practical value. This search is primarily a recreational pursuit. However, the search for Mersenne primes has proved useful in development of new algorithms, testing computer hardware, and interesting young students in math.

Does this affect RSA cryptography?

The security of the RSA algorithm is founded on the mathematical difficulty of finding two prime factors of a very large number. Essentially, a RSA public key is the product of two randomly selected large prime numbers, and the secret key is the two primes themselves. This algorithm is secure because of the great mathematical difficulty of finding the two prime factors of a large number, and of finding the private key from the public key. This is difficult because the only known method of finding the two prime factors of a large number is to check all the possibilities one by one, which isn’t practical because there are so many prime numbers. This means the discovery of a new prime number doesn’t affect the security of RSA. The promised development of quantum computers over the next several decades that can effectively perform many calculations simultaneously may be able to break the RSA algorithm relatively quickly.

Why does the EFF pay $100,000 for this finding?

The foundation supports individual rights on the Internet and set up the prime number prize to promote cooperative computing using the Web.