PRIMES is in P

2004/09/01 by Manindra Agrawal, Neeraj Kayal, Nitin Saxena · 8 citations
Computer Science · Mathematics · #Analytic Number Theory Research #Coding theory and cryptography #Polynomial and algebraic computation

paper · pdf · doi:10.4007/annals.2004.160.781

openalex publication_date 2004/09/01 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/01

Abstract

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

Cited by

• On the Complexity of Computing Prime Tables
• Formalizing an Analytic Proof of the Prime Number Theorem
• Implementing the asymptotically fast version of the elliptic curve primality proving algorithm
• The Nature of Computation
• Primality Testing via Circulant Matrix Eigenvalue Structure: A Novel Approach Using Cyclotomic Field Theory
• Linear degree extractors and the inapproximability of max clique and chromatic number
• On pairs of primes with small order reciprocity
• P versus NP problem [wikipedia]