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

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 $n$ , la criba de Eratóstenes requiere un tiempo de ejecución que es proporcional a $n$ . Por otro lado, la cantidad de dígitos que se necesitan para escribir tal número es proporcional a $\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 $\log ^{k}n$ , si $n$ es un número primo o compuesto. Utilizando la notación O grande, esta proporción se abrevia como ${\mathcal {O}}\left(\log ^{k}n\right)$ . El algoritmo AKS es el primer algoritmo que se conoce con estas características.

Historia

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 $n$ es un número primo la siguiente congruencia se cumple:

$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 $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 ${\mathcal {O}}\left(k\log ^{2}n\right)$ con una probabilidad de error de $1$ en $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: $\left(\log n\right)^{{\mathcal {O}}\left(\log \log \log n\right)}$ . 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.

Fundamentos del algoritmo

El algoritmo AKS está basado en una generalización del pequeño teorema de Fermat hacia los polinomios. El teorema afirma que si $n$ y $a$ son números coprimos, donde $n$ es primo, entonces se cumple la congruencia:

$\left(x+a\right)^{n}\equiv x^{n}+a{\pmod {n}}$

Es decir, si se eleva el polinomio $x+a$ a la potencia $n$ , y luego se divide por $n$ , entonces el residuo de dicha división es $x^{n}+a$ . Más aún, si se cumple esta congruencia entonces $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 $(x+a)^{n}$ requiere más tiempo que la criba de Eratóstenes. En su lugar, se utiliza la congruencia:

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

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

El «orden de un número $a$ módulo $n$ » se denota matemáticamente como $\mathrm {o} _{n}(a)~$ . Representa el más pequeño valor de $k$ para el cual $a^{k}\equiv 1{\pmod {n}}$ . El algoritmo AKS selecciona $r$ como el más pequeño que cumple $\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 $n$ , $r$ y $v$ son enteros positivos, y si $S$ un conjunto finito de enteros, entonces $n$ es una potencia de un número primo siempre y cuando se cumplan las siguientes condiciones:

El $\mathrm {mcd} (n,r)=1~$ .
El $\mathrm {o} _{r}(n)=v~$ .
El $\mathrm {mcd} (n,b-b^{\prime })=1$ para cada par de elementos $b,b^{\prime }$ que pertenecen a $S~$ .
El hecho de que $d~$ divida a $\phi (r)/v~$ , implica que ${\binom {|S|+\phi (r)-1}{|S|}}\geq 2^{2d\left\lfloor {\sqrt {\phi (r)/d}}\right\rfloor }$ .
Para cualquier elemento $b~$ de $S~$ se cumple $(x+b)^{n}=x^{n}+b~$ en el anillo $\mathbb {Z} _{n}\left[x\right]/\left\langle x^{r}-1\right\rangle$ .

Descripción formal

El algoritmo se puede expresar en pseudocódigo como sigue:

Algoritmo AKS: Decide si un número natural $n~$ es un número primo o compuesto
Si existen números naturales $a,b>1~$ tales que $n=a^{b}~$ entonces $n~$ es compuesto Encuentre el más pequeño valor de $r~$ tal que $\mathrm {o} _{r}(n)>\log _{2}^{2}(n)$ Si $1<\mathrm {mcd} (a,n)<n~$ para algún número natural $a\leq r~$ entonces $n~$ es compuesto Si $n\leq r$ entonces $n~$ es primo Para $a~$ desde $1~$ hasta $\left\lfloor {\sqrt {\phi (r)}}\log _{2}(n)\right\rfloor$ haga lo siguiente: Si $\left(x+a\right)^{n}\not \equiv x^{n}+a{\pmod {x^{r}-1,n}}$ entonces $n~$ es compuesto $n~$ es primo

Análisis e implementación

El primer paso se puede efectuar comprobando que ${\left\lfloor {\sqrt[{b}]{n}}\right\rfloor }^{b}\neq n$ para $b=2,3,4,\ldots ,\left\lfloor \log _{2}n\right\rfloor$ . Esto requiere un tiempo ${\tilde {\mathcal {O}}}(\log ^{3}n)$ .
El segundo paso se puede implementar buscando al primer valor de $r$ que verifique $n^{k}\not \equiv 1{\pmod {r}}$ para cualquier valor de $k=1,2,3,\ldots ,\left\lfloor \log _{2}^{2}(n)\right\rfloor$ . Como $r\leq \lceil \log _{2}^{5}n\rceil$ , entonces este paso se efectúa en un tiempo ${\tilde {\mathcal {O}}}\left(\log ^{7}n\right)$ .
En el tercer paso se puede utilizar el algoritmo de Euclides para buscar el máximo común divisor de dos números. Dado que se necesitan calcular $r~$ de estos valores, el tiempo necesario es ${\mathcal {O}}(\log ^{6}n)$ .
En el cuarto paso solo se necesita comparar los dígitos. Esto necesita un tiempo ${\mathcal {O}}(\log n)$ .
El quinto paso es el más lento de todos. Se puede utilizar una variante de la exponenciación binaria para calcular la parte izquierda de cada congruencia. Se necesitan calcular $\left\lfloor {\sqrt {\phi (r)}}\log _{2}(n)\right\rfloor$ de estas congruencias. Por lo tanto este paso requiere un tiempo ${\tilde {\mathcal {O}}}\left(\log ^{21/2}n\right)$ .

Por lo tanto el algoritmo AKS requiere un tiempo ${\tilde {\mathcal {O}}}\left(\log ^{21/2}n\right)$ . 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 ${\tilde {\mathcal {O}}}(\log ^{6}n)$ . Este tiempo se podría demostrar siempre y cuando se demuestre la conjetura de los números primos gemelos.

Referencias

Manindra Agrawal, Neeraj Kayal, Nitin Saxena (2004). «PRIMES is in P». Annals of Mathematics 160 (2). ISSN 0003-486X , 781-793.
Folkmar Bornemann (2003). «PRIMES Is in P: A Breakthrough for "Everyman"». Notices of the AMS 50 (5). ISSN 0002-9920 , 545-552.
José de Jesús Angel Angel, Guillermo Morales-Luna (2008). «El algoritmo de Agrawal, Kayal y Saxena para decidir primalidad». Carta Informativa, Sociedad Matemática Mexicana (55). (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última).
Bernstein, Daniel (2003). Proving primality after Agrawal-Kayal-Saxena. Preprint.
Crandall, R; Papadopoulos, J (2003). «On the implementation of AKS-class primality tests». Advanced Computation Group.

Enlaces externos

Datos: Q294284