Test de primalidad AKS

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

1 El problema de la primalidad

2 Historia

3 Fundamentos del algoritmo

4 Descripción formal

5 Análisis e implementación

6 Referencias

7 Enlaces externos

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^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 $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:

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

Si existen números naturales $a~$ y $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_2n\right\rfloor$ . 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 $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 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 $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 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

The AKS "PRIMES in P" Algorithm Resource

Finding primes & proving primality

Categoría:
Tests de primalidad

Algoritmo AKS: Decide si un número natural $n~$ es un número primo o compuesto
Si existen números naturales $a~$ y $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

Игры ⚽ Поможем решить контрольную работу

Mira otros diccionarios:

Test de primalidad — El 39º número primo de Mersenne era el mayor conocido hasta la fecha de creación de este artículo. La cuestión de la determinación de si un número n … Wikipedia Español
Análisis de primalidad AKS — Saltar a navegación, búsqueda 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,… … 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
Hipótesis generalizada de Riemann — La hipótesis de Riemann es una de las conjeturas más importantes de la matemáticas. Es un postulado sobre los ceros de la función zeta de Riemann. Existen varios objetos geométricos y aritméticos que pueden ser descritos por las llamadas… … 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
Nitin Saxena — (en hindi: नितन सक्सेना) (n. 3 de mayo de 1981 en Allahabad)[1] es un informático teórico indio. Junto con Manindra Agrawal y Neeraj Kayal propusieron el Test de primalidad AKS en 2002, trabajo por el cual ganaron el Premio Gödel en 2006. Esta… … Wikipedia Español
Complejidad y criptografía — La criptografía es la ciencia encargada del estudio y diseño de sistemas que permiten ocultar información. Desde sus inicios, esta capacidad de encubrimiento se ha basado en la dificultad que supondría a una entidad no autorizada el obtener la… … Wikipedia Español
Algoritmo determinista — En ciencias de la computación, un algoritmo determinista es un algoritmo que, en términos informales, es completamente predictivo si se conocen sus entradas. Dicho de otra forma, si se conocen las entradas del algoritmo siempre producirá la misma … Wikipedia Español

Los diccionarios y las enciclopedias sobre el Académico

Test de primalidad AKS

Contenido

El problema de la primalidad

Historia

Fundamentos del algoritmo

Descripción formal

Análisis e implementación

Referencias

Enlaces externos

Mira otros diccionarios:

Compartir el artículo y extractos

Los diccionarios y las enciclopedias sobre el Académico

Wikipedia Español

Test de primalidad AKS

Contenido

El problema de la primalidad

Historia

Fundamentos del algoritmo

Descripción formal

Análisis e implementación

Referencias

Enlaces externos

Mira otros diccionarios:

Compartir el artículo y extractos

Link directo