brainwagon

RSA encryption relies on being able to find large primes. For quite some time, the Miller-Rabin test has been known to be able to determine whether a given number is prime with as great a likelihood as you wish (say, with likelihood of error much lower than the chances that your computer made a mistake). Thus the claim was that primality testing was very likely in P, although no algorithm for primality testing in P was known. Until now.

Manindra Agrawal from the Indian Institute of Technology Kanpur CS department has a paper which claims to give a primality testing algorithm that is polynomial time. I haven’t had time yet to review it, but it is a very interesting result.

Undoubtably the Chicken Littles of the world will run around crying that the sky is falling for RSA encryption. It must be emphasized that this is an algorithm for primality testing. Primality testing is thought to be significantly easier than factoring. If a factoring algorithm was found in P, that would truly
be surprising, as well as likely fatal to RSA based encryption.