Test de primalidad AKS: PRIMOS está en P
AKS primality test
- Fecha
- 2002 · fiabilidad alta
- Lugar
- Kanpur (IIT), India
- Autoría
- Manindra Agrawal, Neeraj Kayal y Nitin Saxena
- Personas
- 👤 Manindra Agrawal1966–👤 Neeraj Kayal2000–👤 Nitin Saxena1981–
- Ámbito
- Saber y símbolos
Qué se descubrió
Primer algoritmo determinista de tiempo polinómico que decide si un número es primo, sin depender de hipótesis no probadas. Cierra una cuestión abierta desde Gauss.
Kayal y Saxena eran estudiantes de grado; en la práctica siguen usándose tests probabilísticos más rápidos.
A qué dio paso
- teoría de la complejidad
- teoría algorítmica de números
Se apoya en
- Pequeño teorema de Fermat1640
- tests de Miller-Rabin
- criptografía RSA