AKS primality test
Test de primalidad AKS: PRIMOS está en P
- Date
- 2002 · confidence high
- Place
- Kanpur (IIT), India
- Credited to
- Manindra Agrawal, Neeraj Kayal and Nitin Saxena
- People
- 👤 Manindra Agrawal1966–👤 Neeraj Kayal2000–👤 Nitin Saxena1981–
- Field
- Knowledge & symbols
What was discovered
The first deterministic polynomial-time algorithm that decides whether a number is prime, without relying on unproven hypotheses. It closes a question open since Gauss.
Kayal and Saxena were undergraduate students; in practice, faster probabilistic tests are still used.
What it led to
- complexity theory
- algorithmic number theory
Built on
- Fermat's little theorem1640
- Miller-Rabin tests
- RSA cryptography