PRIMES is in P

Abstract

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

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