Test de primalidad AKS

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. Su descubrimiento pone fin a uno de los más grandes problemas de la teoría de números y teoría de la complejidad computacional.

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. Para decidir la primalidad de un número ${displaystyle n}$, la criba de Eratóstenes requiere un tiempo de ejecución que es proporcional a ${displaystyle n}$. Por otro lado, la cantidad de dígitos que se necesitan para escribir tal número es proporcional a ${displaystyle log(n)}$.

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 ${displaystyle log ^{k}n}$, si ${displaystyle n}$ es un número primo o compuesto. Utilizando la notación O grande, esta proporción se abrevia como ${displaystyle {mathcal {O}}left(log ^{k}n ight)}$. El algoritmo AKS es el primer algoritmo que se conoce con estas características.

Antes de que Agrawal, Kayal y Saxena describieran su algoritmo, se hicieron muchos intentos por resolver el problema de la primalidad de manera eficiente. 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. Dicho teorema afirma que cuando ${displaystyle n}$ es un número primo la siguiente congruencia se cumple:

${displaystyle a^{n}equiv a{pmod {n}}}$

Este teorema se tomó como fundamento de varios tests de primalidad.

El test de primalidad de Miller-Rabin fue presentado en 1980. El algoritmo sí funciona en tiempo polinomial, pero es probabilista. Por ejemplo, después de realizar el test de Miller-Rabin ${displaystyle k}$ veces, el algoritmo o bien expide un certificado de que el número es compuesto o bien afirma que el número tiene una alta probabilidad de ser primo. El test de Miller-Rabin requiere un tiempo ${displaystyle {mathcal {O}}left(klog ^{2}n ight)}$ con una probabilidad de error de ${displaystyle 1}$ en ${displaystyle 4^{k}}$.

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: ${displaystyle left(log n ight)^{{mathcal {O}}left(log log log n ight)}}$. 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. El teorema afirma que si ${displaystyle n}$ y ${displaystyle a}$ son números coprimos, donde ${displaystyle n}$ es primo, entonces se cumple la congruencia:

${displaystyle left(x+a ight)^{n}equiv x^{n}+a{pmod {n}}}$

Es decir, si se eleva el polinomio ${displaystyle x+a}$ a la potencia ${displaystyle n}$, y luego se divide por ${displaystyle n}$, entonces el residuo de dicha división es ${displaystyle x^{n}+a}$. Más aún, si se cumple esta congruencia entonces ${displaystyle n}$ debe ser un número primo.

A pesar de que esta congruencia caracteriza por completo a los números primos, no es factible aplicarla dado que el cálculo de ${displaystyle (x+a)^{n}}$ requiere más tiempo que la criba de Eratóstenes. En su lugar, se utiliza la congruencia

${displaystyle left(x+a ight)^{n}equiv x^{n}+a{pmod {x^{r}-1,n}}}$

Es decir, la equivalencia entre los residuos de los polinomios ${displaystyle (x+a)^{n}}$ y ${displaystyle x^{n}+a}$ después de haber sido divididos por ${displaystyle x^{r}-1}$ y a su vez cada coeficiente por ${displaystyle n}$. En lenguaje matemático se abrevia como ${displaystyle (x+a)^{n}=x^{n}+a}$ en el anillo ${displaystyle mathbb {Z} _{n}left[x ight]/leftlangle x^{r}-1 ight angle }$. Algunos números compuestos ${displaystyle n}$ satisfacen esta congruencia, pero si se elige ${displaystyle r}$ de manera adecuada y se cumple la congruencia para varios números ${displaystyle a}$, entonces ${displaystyle n}$ debe ser o un número primo o al menos una potencia de un número primo.

El "orden de un número ${displaystyle a}$ módulo ${displaystyle n}$" se denota matemáticamente como ${displaystyle mathrm {o} _{n}(a)~}$. Representa el más pequeño valor de ${displaystyle k}$ para el cual ${displaystyle a^{k}equiv 1{pmod {n}}}$. El algoritmo AKS selecciona ${displaystyle r}$ como el más pequeño que cumple ${displaystyle mathrm {o} _{r}(n)>log _{2}^{2}(n)}$ (véase Logaritmo binario).

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. y Bernstein. En su forma más sencilla, dicho teorema afirma que si ${displaystyle n}$, ${displaystyle r}$ y ${displaystyle v}$ son enteros positivos, y si ${displaystyle S}$ un conjunto finito de enteros, entonces ${displaystyle n}$ 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 ${displaystyle { ilde {mathcal {O}}}left(log ^{21/2}n ight)}$. Es decir, el algoritmo AKS resuelve el problema de la primalidad de manera determinista y en un tiempo polinómico. En la práctica, el algoritmo parece correr en un tiempo ${displaystyle { ilde {mathcal {O}}}(log ^{6}n)}$. Este tiempo se podría demostrar siempre y cuando se demuestre la conjetura de los números primos gemelos.