Prueba de primalidad de AKS
La prueba de primalidad AKS (también conocida como prueba de primalidad Agrawal-Kayal-Saxena y prueba AKS ciclotómica ) es un algoritmo determinista de prueba de primalidad creado y publicado por Manindra Agrawal , Neeraj Kayal y Nitin Saxena , científicos informáticos del Instituto Indio de Tecnología de Kanpur. , el 6 de agosto de 2002, en un artículo titulado "PRIMES está en P". [1] El algoritmo fue el primero que puede determinar de manera comprobable si un número dado es primo o compuesto en tiempo polinomial , sin depender deconjeturas matemáticas como la hipótesis generalizada de Riemann . La prueba también se destaca por no apoyarse en el campo de análisis . [2] En 2006, los autores recibieron el premio Gödel y el premio Fulkerson por su trabajo.
AKS es el primer algoritmo de prueba de primalidad que es simultáneamente general , de tiempo polinómico , determinista e incondicionalmente correcto . Los algoritmos anteriores se habían desarrollado durante siglos y lograban tres de estas propiedades como máximo, pero no las cuatro.
Si bien el algoritmo es de inmensa importancia teórica, no se utiliza en la práctica, lo que lo convierte en un algoritmo galáctico . Para entradas de 64 bits, la prueba de primalidad Baillie-PSW es determinista y se ejecuta muchos órdenes de magnitud más rápido. Para entradas más grandes, el rendimiento de las pruebas ECPP y APR (también incondicionalmente correctas) es muy superior al de AKS. Además, ECPP puede generar un certificado de primalidad que permite una verificación independiente y rápida de los resultados, lo que no es posible con el algoritmo AKS.
La prueba de primalidad de AKS se basa en el siguiente teorema: Dado un entero y un entero coprimo de , es primo si y solo si la relación de congruencia polinomial
se mantiene dentro del anillo polinomial . [1] Nótese que denota el indeterminado que genera este anillo polinomial.
![{\ Displaystyle \ mathbb {Z} _ {n} [X]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/82135e036b2faf791a49f60d054df9d8ac2c53e5)
Este teorema es una generalización a polinomios del pequeño teorema de Fermat . En una dirección, se puede demostrar fácilmente utilizando el teorema del binomio junto con la siguiente propiedad del coeficiente binomial :