FOM: Primality is in P

Anatoly Vorobey mellon at pobox.com
Wed Aug 7 11:59:59 EDT 2002


Hello Piyush,

PPK>         Last sunday we received a communication from Prof Manindra Agrawal,
PPK> IIT Kanpur India, saying that the problem of testing whether a number is
PPK> prime has been shown to be in P. They ( Manindra Agrawal, Neeraj Kayal and
PPK> Nitin Saxena) have given and $O( (log n)^12 )$ algorithm for primality.

Their paper is available here:

http://www.cse.iitk.ac.in/primality.pdf
-- 
Anatoly Vorobey,
my journal (in Russian): http://www.livejournal.com/users/avva/
mellon at pobox.com http://pobox.com/~mellon/
"Angels can fly because they take themselves lightly" - G.K.Chesterton





More information about the FOM mailing list