Student Discovers Largest Known Prime Number

DETROIT — More than 200,000 computers spent years looking for the largest known prime number (search). It turned up on Michigan State University (search) graduate student Michael Shafer's off-the-shelf PC.

"It was just a matter of time," Shafer said.

The number is 6,320,430 digits long and would need 1,400 to 1,500 pages to write out. It is more than 2 million digits larger than the previous largest known prime number.

Shafer, 26, helped find the number as a volunteer on an eight-year-old project called the Great Internet Mersenne Prime Search (search).

Tens of thousands of people volunteered the use of their PCs in a worldwide project that harnessed the power of 211,000 computers, in effect creating a supercomputer capable of performing 9 trillion calculations per second. Participants could run the mathematical analysis program on their computers in the background, as they worked on other tasks.

Shafer ran an ordinary Dell computer in his office for 19 days until Nov. 17, when he glanced at the screen and saw "New Mersenne prime found."

A prime number is a positive number divisible only by itself and one: 2, 3, 5, 7 and so on. Mersenne primes are a special category, expressed as 2 to the "p" power minus 1, where "p" also is a prime number.

In the case of Shafer's discovery, it was 2 to the 20,996,011th power minus 1. The find was independently verified by other participants in the project.

Mersenne primes are rare but are critical to the branch of mathematics called number theory. That said, what is the practical significance of Shafer's number?

You can see the full story here:

http://www.foxnews.com/story/0,2933,105383,00.html

I actually first heard about people searching for larger prime numbers in one of my math classes in college. If I recall there is actually a very good reason they are searching for higher prime numbers. If I remember, they are able to use them to make better encrypting algorithms. I may be wrong, but for some reason I remember some kind of discussion on that. I remember discussion on PGP too.

Factoring N would clearly enable RSA to be broken. It has not been proven that there is no polynomial time solution to finding prime factors of large numbers (i.e. it is possible that an algorithm that could factor N quickly enough to break RSA may be discovered in the future). However, despite constant improvements in factoring algorithms none have been found that satisfy the polynomial-time criteria which would make cracking RSA a tractable problem.
It is important to note that it has not been proven that security of RSA relies solely on the mathematical diffculty of finding the prime factors of large numbers. However, many of the other possibilities for finding D given E have been shown to be of equivalent difficulty to factoring N. One possibility is that an algorithm could be devised to find the Eth root mod N more easily than factoring N. Nevertheless, no such algorithm has been discovered so far, and RSA has withstood many attempts to crack it.

Found that on this page:

http://www.momentus.com.br/PGP/doc/howpgp.html

Sounds like the fact that prime numbers are so hard to find, is how PGP works so good.

The larger the numbers increase, the smaller amount of primes that can be found. In other words the overall distance between prime numbers keeps increasing. However every now and then they will find a 2 huge prime numbers that are within 2 from each other. I forget what kind of prime numbers those are called, but there is a special name for them.