Prueba de primalidad AKS

---

La prueba de primalidad AKS (también conocida como prueba de primalidad Agrawal-Kayal-Saxena y prueba AKS ciclotómica ) es un algoritmo de prueba de primalidad determinista creado y publicado por Manindra Agrawal , Neeraj Kayal y Nitin Saxena , informáticos del Instituto Indio de Tecnología de Kanpur. , el 6 de agosto de 2002, en un artículo titulado "PRIMES is in P". ^[1] El algoritmo fue el primero que pudo determinar si un número dado es primo o compuesto en tiempo polinomial , sin depender de conjeturas matemáticas como la hipótesis generalizada de Riemann . La prueba también se destaca por no depender del campo de análisis . ^[2] En 2006 los autores recibieron tanto el Premio Gödel como el Premio Fulkerson por su trabajo.

AKS es el primer algoritmo de prueba de primalidad que es simultáneamente general , de tiempo polinomial , determinista e incondicionalmente correcto . Los algoritmos anteriores se habían desarrollado durante siglos y lograban como máximo tres de estas propiedades, pero no las cuatro.

Si bien el algoritmo tiene una importancia teórica inmensa, no se usa en la práctica, lo que lo convierte en un algoritmo galáctico . Para entradas de 64 bits, la prueba 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 AKS. Además, ECPP puede emitir 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 AKS se basa en el siguiente teorema: Dado un número entero y un número entero coprimo de , es primo si y solo si la relación de congruencia polinomial${\ estilo de visualización n \ geq 2}$${\ estilo de visualización a}$ ${\ estilo de visualización n}$${\ estilo de visualización n}$

se mantiene dentro del anillo polinomial . ^[1] Tenga en cuenta que denota el indeterminado que genera este anillo polinomial.${\ estilo de visualización \ mathbb {Z} _ {n} [X]}$${\ estilo de visualización X}$

Este teorema es una generalización a polinomios del pequeño teorema de Fermat . En una dirección, se puede demostrar fácilmente usando el teorema del binomio junto con la siguiente propiedad del coeficiente del binomio :

---