Análisis de primalidad AKS

Análisis de primalidad AKS

Análisis de primalidad AKS

El análisis 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 de la á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 logkn, 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^kn\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 y a es un número coprimo de n, la siguiente congruencia se cumple:

a^n\equiv a\pmod n

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 \mathcal O\left(k\log^2n\right) 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: \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 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

\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 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 \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:

  • \mathrm{mcd}(n,r)=1~
  • \mathrm o_r(n)=v~
  • \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
  1. Si existen números naturales a~ y b>1~ tales que n=a^b~ entonces n~ es compuesto
  2. Encuentre el más pequeño valor de r~ tal que \mathrm o_r(n) > \log_2^2(n)
  3. Si 1<\mathrm{mcd}(a,n)<n~ para algún número natural a\leq r~ entonces n~ es compuesto
  4. Si n\leq r entonces n~ es primo
  5. Para a~ desde 1~ hasta \left\lfloor\sqrt{\phi(r)}\log_2(n)\right\rfloor haga lo siguiente:
    1. Si \left(x+a\right)^n\not\equiv x^n+a\pmod{x^r-1,n} entonces n~ es compuesto
  6. 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_2n\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 a^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^5_2n\rceil, entonces este paso se efectúa en un tiempo \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 r~ de estos valores, el tiempo necesario es \mathcal O(\log^6n)
  • En el cuarto paso sólo 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

Enlaces externos

Obtenido de "An%C3%A1lisis de primalidad AKS"

Wikimedia foundation. 2010.

Игры ⚽ Нужен реферат?

Mira otros diccionarios:

  • 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… …   Wikipedia Español

  • Número primo — Un número primo es un número natural mayor que 1, que tiene únicamente dos divisores distintos: él mismo y el 1. Se contraponen así a los números compuestos, que son aquellos que tienen algún divisor natural aparte de sí mismos y del 1. El número …   Wikipedia Español

  • Premio Gödel — Saltar a navegación, búsqueda El Premio Gödel es un premio que se entrega a autores de artículos relacionados con teoría de la computación. El nombre del premio se debe al matemático Kurt Gödel, y es otorgado por la European Association for… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”