From the Orient

PRIMES is in P (from New Scientist)

“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.”

Eratosthenes came up with the first foolproof way of telling if a number is prime back in 240 BC, but the time the method took grew exponentially with the size of number, so for numbers the size that cryptography use, you’d need longer than the age of the universe to find out if the number is prime.

This new solution is the first to give the answer in a resonable amount of time. This doesn’t really affect cryptography as it doesn’t offer a real advantage over current methods that estimate the probability of whether a number is prime or not.

But as Carl Pomerance of Bell Labs points out “If there is a simple test for primality, there may well be a simple way to determine prime factors that we’re currently overlooking”