- 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.
Contenido
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 kn, si n es un número primo o compuesto. Utilizando la notación O grande, esta proporción se abrevia como
. 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 y a es un número coprimo de n, la siguiente congruencia se cumple:
Significa que si se eleva el número a a la potencia n y luego se divide entre n, el residuo de esta división es precisamente a. 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
con una probabilidad de error de 1 en 4k.
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.
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
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 xn + 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
Es decir, la equivalencia entre los residuos de los polinomios (x + a)n y xn + a después de haber sido divididos por xr − 1 y a su vez cada coeficiente por n. En lenguaje matemático se abrevia como (x + a)n = xn + a en el anillo
. 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
. Representa el más pequeño valor de k para el cual
. El algoritmo AKS selecciona r como el más pequeño que cumple
(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:
para cada par de elementos
que pertenecen a
- El hecho de que
divida a
, implica que
- Para cualquier elemento
de
se cumple
en el anillo
Descripción formal
El algoritmo se puede expresar en pseudocódigo como sigue:
Algoritmo AKS: Decide si un número natural es un número primo o compuesto
- Si existen números naturales
y
tales que
entonces
es compuesto
- Encuentre el más pequeño valor de
tal que
- Si
para algún número natural
entonces
es compuesto
- Si
entonces
es primo
- Para
desde
hasta
haga lo siguiente:
- Si
entonces
es compuesto
- Si
es primo
Análisis e implementación
- El primer paso se puede efectuar comprobando que
para
. Esto requiere un tiempo No se pudo entender (La conversión a PNG ha sido errónea): \tilde\mathcal O(\log^3 n)
- El segundo paso se puede implementar buscando al primer valor de r que verifique
para cualquier valor de
. Como
, entonces este paso se efectúa en un tiempo No se pudo entender (La conversión a PNG ha sido errónea): \tilde\mathcal O\left(\log^7n\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
de estos valores, el tiempo necesario es
- En el cuarto paso sólo se necesita comparar los dígitos. Esto necesita un tiempo
- 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
de estas congruencias. Por lo tanto este paso requiere un tiempo No se pudo entender (La conversión a PNG ha sido errónea): \tilde\mathcal O\left(\log^{21/2}n\right)
Por lo tanto el algoritmo AKS requiere un tiempo No se pudo entender (La conversión a PNG ha sido errónea): \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 No se pudo entender (La conversión a PNG ha sido errónea): \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. http://annals.princeton.edu/annals/2004/160-2/p12.xhtml.
- Folkmar Bornemann (2003). «PRIMES Is in P: A Breakthrough for "Everyman"». Notices of the AMS 50 (5). ISSN 0002-9920 , 545-552. http://www.ams.org/notices/200305/fea-bornemann.pdf.
- 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). http://smm.org.mx/publicaciones/carta/2008/enero/pdf/smm-carta-inf-2008-enero.pdf.
- Bernstein, Daniel (2003). Proving primality after Agrawal-Kayal-Saxena. Preprint. http://cr.yp.to/papers/aks.pdf.
- Crandall, R; Papadopoulos, J (2003). «On the implementation of AKS-class primality tests». Advanced Computation Group. http://developer.apple.com/hardware/ve/pdf/aks3.pdf.
Enlaces externos
Categoría:- Tests de primalidad
Wikimedia foundation. 2010.