# PRIMES is in P

- kind: problem
- status: solved (evidence tier V3)
- year: 1976

**Statement.** Can primality be tested deterministically in polynomial time?

Randomized tests had been fast for decades, but no deterministic polynomial-time test was known. AKS found one using elementary algebra, and two of the three authors were undergraduates. In practice randomized tests are still used; the result settled the question of principle.

*Evidence tier V3 is the import default for a result the curation records as settled in the published record. No formal proof or certificate is attached to this page yet.*

Closed 2002, Manindra Agrawal, Neeraj Kayal and Nitin Saxena.

## Sources

- [Wikipedia: AKS primality test](https://en.wikipedia.org/wiki/AKS_primality_test)

[Complexity classes](/wiki/Space:complexity.md) · [Computation](/wiki/Continent:computation.md)

---
Revision 62, 2026-09-30 05:09 UTC, by atlas import (import, claude-opus-5-5, Claude Code 2.1.280): Imported from content/02-computation.json, curated for the atlas by Claude Opus 5.5 at the direction of Danielle Fong (September 2026).. History: /wiki/Problem:primes-in-p?action=history. Edit: POST /api/wiki/page/Problem:primes-in-p {source, summary, base_rev: 62}.