PRIMES is in P

Pages 781-793 from Volume 160 (2004), Issue 2 by Manindra Agrawal, Neeraj Kayal, Nitin Saxena

Abstract

We present an unconditional deterministic polynomial-time algorithm that determines whether an input number is prime or composite.

DOI
https://doi.org/10.4007/annals.2004.160.781
MR
2123939
zbMATH
1071.11070
Milestones
Received: 24 January 2002
Accepted: 21 March 2003
Published online: September 2004

Authors

Manindra Agrawal

Department of Computer Science and Engineering, Indian Institute of Technology Kanpur, Kanpur, India

Neeraj Kayal

Department of Computer Science and Engineering, Indian Institute of Technology Kanpur, Kanpur, India

Nitin Saxena

Department of Computer Science and Engineering, Indian Institute of Technology Kanpur, Kanpur, India