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