Pete Finnigan's Oracle Security Weblog

I was in a position last week where I needed to wait for a meeting with someone for two hours so I bought a bottle of water and the latest copy of New Scientist, which I have not bought for a few years. I used to buy it regularly. I picked it mainly because of one article but I found quite a lot of interesting stuff in there.

The article I was interested in was titled "The prime number hunters close in" by Ian Stewart and it was published 6 August 2005 (in the UK). There is a brief summary of this paper on the link I have just given. To read the rest of the article you need to subscribe or buy the paper copy like I did.

Basically the article says that in the past the hunt for ever bigger prime numbers has hit limits that are basically never going to be passed. The methods used for bigger numbers involve probabilistic checks. The hunt has been on for a better efficient test for the factors of primes. This looks like it could have been found thanks to the brains of Manindra Agrawal and his students Neeraj Kayal and Nitin Saxena at the Indian Institute of Technology, Kanpur. The method looks like it might have a practical implementation some day.

This has implications for cryptography that is based on primes such as RSA. It was thought impossible that a practical method could be found to locate primes but that looks like it was wrong, the same is said of cracking the codes used in algorithms such as RSA, could they also be wrong about this? - could cryptography not be as secure as was previously thought?