Prof. Manindra Agarwal and two of his students, Nitin Saxena and Neeraj Kayal (both BTech from CSE/IITK who have just joined as Ph.D. students), have discovered a polynomial time deterministic algorithm to test if an input number is prime or not. Lots of people over (literally!) centuries have been looking for a polynomial time test for primality, and this result is a major breakthrough, likened by some to the P-time solution to Linear Programming announced in the 70s. [Indian Institute of Technology Kanpur]
Though this breakthrough doesn’t have any short-term impact (current methods for discovering prime numbers are faster), it appears to be foolproof. This is important because many current security mechanisms (i.e., encryption) depend on prime numbers to remain difficult (if not impossible) to crack. Problems with current methods of picking prime numbers are that the larger the numbers get, the harder it is to know for certain that the number is a prime. Assuming that Agarwal’s discovery will lead to others who can improve upon it, this bodes well for future cryptographers (which will necessarily benefit anyone relying on secure communications).
No comments:
Post a Comment