Вот, попалось на глаза такое сообщение.

Turns out, Primes are in P

Manindra Agrawal et. al. of the Indian Institute of Technology Kanpur CS department have released a most interesting paper today. It presents an algorithm that determines whether a number is prime or not in polynomial time. While I haven't gone through the presentation in detail, it looks like a promising, albeit non-optimized, solution for the famous PRIMES in P problem.

http://www.cse.iitk.ac.in/primality.pdf