Primality (Teddy Bloggie Blog Blogging)

I wish I understood enough math to make sense of all the great new discoveries happening in science and mathematics. I never even took a class on number theory... Today's NY Times has me thinking about our endless search for answers in nature - the cryptic way it talks to us. Here's an excerpt:

From Here to Infinity: Obsessing With the Magic of Primes By GEORGE JOHNSON There are practical reasons you would not want to smash atoms in your basement, observing for yourself the peculiar behavior of the fundamental components of matter. But studying primes, those mathematical quarks from which all numbers are made, is a game anyone can play. The only hazard is that it is easy to become obsessed, even for a nonmathematician.

It was early August, just after three computer scientists from India sent rumbles through the mathematical world with a new discovery about primes � numbers like 7, 23 and 1,299,007 that are divisible by only themselves and 1. And there I sat, reading about the implications on an Internet rumor-mill called Slashdot.org while listening for inspiration to an eerie John Cage-like musical composition derived from the first 18,000 primes....
...That is where the Indian computer scientists' discovery comes in. For years mathematicians have been able to take very long numbers � so long that they could not be factored in any reasonable time � and run them through a kind of primality testing machine: an algorithm that can say, with a very high likelihood, whether the number is fissionable.

This is good enough for practical purposes. These highly probable "industrial grade" primes are used on the Internet to generate the keys that encode secret messages. But, for mostly theoretical reasons, mathematicians had long wondered whether there was an efficient way to tell with absolute certainty that any number was prime.

The answer, they now know, is yes. In a preprint posted at www.cse.iitk.ac.in/news/primality.html, Dr. Manindra Agrawal and his students Neeraj Kayal and Nitin Saxena of the Indian Institute of Technology in Kanpur offer a foolproof primality-testing algorithm that runs in "polynomial time." As it examines longer and longer numbers, the computing time increases but not so drastically as to overwhelm the machine...

If anyone out there would like to explain the following proof to me, I'd really appreciate it. Follow the link for the proof: Search for Primes