El test de primalidad AKS o algoritmo AKS es un algoritmo determinista que decide en tiempo polinómico si un número natural es primo o compuesto.
Fue diseñado por los científicos de computación Manindra Agrawal, Neeraj Kayal y Nitin Saxena del Instituto tecnológico hindú de Kanpur en el año 2002, y eventualmente mejorado por otros investigadores del área.
El problema de la primalidad consiste en averiguar si un número natural es primo o compuesto.
Hay métodos muy antiguos para resolver este problema como la criba de Eratóstenes (200 a. C.) o la división por tentativa, sin embargo estos métodos resultan ineficaces cuando se desea analizar números grandes.
Por otro lado, la cantidad de dígitos que se necesitan para escribir tal número es proporcional a
En términos de complejidad computacional, se dice que un método eficaz debería requerir un tiempo polinómico respecto a la cantidad de dígitos.
En este caso se desea tener un algoritmo que decida en un tiempo proporcional a
Utilizando la notación O grande, esta proporción se abrevia como
En 1798 Gauss sugirió que para distinguir a los números primos de los números compuestos no era necesario descomponer en factores a estos últimos.
En 1636 Fermat presentó su célebre pequeño teorema de Fermat con el cual se dio a conocer una característica que cumplen todos los números primos.
es un número primo la siguiente congruencia se cumple:
El algoritmo sí funciona en tiempo polinomial, pero es probabilista.
En 1983 Leonard Adleman, Carl Pomerance, y Robert Rumely crearon un test de primalidad que sí es determinista pero cuyo tiempo de ejecución era exponencial:
Su algoritmo está basado en teoría muy compleja y una generalización del pequeño teorema de Fermat hacia los números enteros en campos ciclotómicos.
Sin embargo, este algoritmo es tan rápido que durante mucho tiempo se usaron variantes para romper marcas en cuanto a comprobar la primalidad de números con más de mil cifras decimales.
A pesar de este gran logro, todavía existía la pregunta de si existe algún algoritmo que funcione en tiempo polinómico y que fuera determinista.
En 1992 surgieron otra clase algoritmos basados en curvas elípticas, pero que tampoco eran deterministas.
Finalmente, en 1999 Manindra Agrawal estudió una variante del pequeño teorema de Fermat.
Dos años después, él y sus dos estudiantes del IITK comenzaron a analizar todas las propiedades de esta variante hasta que encontraron una caracterización completa de los números primos.
Con base en esta caracterización, en el año 2002 presentaron su algoritmo en el artículo PRIMES is in P. El algoritmo AKS está basado en una generalización del pequeño teorema de Fermat hacia los polinomios.
Es decir, si se eleva el polinomio
Más aún, si se cumple esta congruencia entonces
A pesar de que esta congruencia caracteriza por completo a los números primos, no es factible aplicarla dado que el cálculo de
requiere más tiempo que la criba de Eratóstenes.
satisfacen esta congruencia, pero si se elige
de manera adecuada y se cumple la congruencia para varios números
Además de esto, el algoritmo también requiere conocer la función de Euler y el máximo común divisor.
La corrección del algoritmo está garantizada por un teorema que originalmente fue demostrado por los autores y posteriormente resumido por Lenstra, Jr.
En su forma más sencilla, dicho teorema afirma que si
es una potencia de un número primo siempre y cuando se cumplan las siguientes condiciones: El algoritmo se puede expresar en pseudocódigo como sigue: Por lo tanto el algoritmo AKS requiere un tiempo