Prueba de primacía AKS

La prueba de primalidad AKS (también conocida como prueba de primalidad Agrawal-Kayal-Saxena y prueba AKS ciclotómica ) es un algoritmo determinista de prueba de primalidad creado y publicado por Manindra Agrawal , Neeraj Kayal y Nitin Saxena , científicos informáticos del Instituto Indio de Tecnología de Kanpur , el 6 de agosto de 2002, en un artículo titulado "PRIMES is in P". ^{[ 1 ]} El algoritmo fue el primero capaz de determinar en tiempo polinomial si un número dado es primo o compuesto sin depender de conjeturas matemáticas como la hipótesis generalizada de Riemann . La prueba también es notable por no depender del campo del análisis . ^{[ 2 ]} En 2006, los autores recibieron el Premio Gödel y el Premio Fulkerson por su trabajo.

AKS es el primer algoritmo de prueba de primalidad que es simultáneamente general , de tiempo polinomial , determinista e incondicionalmente correcto . Los algoritmos anteriores se habían desarrollado durante siglos y, como máximo, lograban tres de estas propiedades, pero no las cuatro.

• El algoritmo AKS se puede utilizar para verificar la primalidad de cualquier número general dado. Se conocen muchas pruebas de primalidad rápidas que funcionan solo para números con ciertas propiedades. Por ejemplo, la prueba de Lucas-Lehmer funciona solo para números de Mersenne , mientras que la prueba de Pépin se puede aplicar solo a números de Fermat .
• El tiempo máximo de ejecución del algoritmo puede estar limitado por un polinomio sobre el número de dígitos del número objetivo. Los algoritmos ECPP y APR demuestran o refutan de forma concluyente que un número dado es primo, pero se desconoce si tienen límites de tiempo polinomiales para todas las entradas.
• El algoritmo garantiza la distinción determinista entre el número objetivo y un número compuesto. Las pruebas aleatorias, como Miller-Rabin y Baillie-PSW , pueden comprobar la primalidad de cualquier número en tiempo polinomial, pero se sabe que solo producen un resultado probabilístico.
• La corrección de AKS no depende de ninguna hipótesis subsidiaria no probada . En cambio, la versión de Miller de la prueba de Miller-Rabin es totalmente determinista y se ejecuta en tiempo polinomial sobre todas las entradas, pero su corrección depende de la veracidad de la hipótesis generalizada de Riemann, aún no probada .

Si bien el algoritmo tiene una importancia teórica inmensa, no se utiliza en la práctica, lo que lo convierte en un algoritmo de alcance limitado . Para entradas de 64 bits, la prueba Baillie-PSW es ​​determinista y se ejecuta mucho más rápido. Para entradas de mayor tamaño, el rendimiento de las pruebas ECPP y APR (que también son incondicionalmente correctas) es muy superior al de AKS. Además, ECPP puede generar un certificado de primalidad que permite una verificación independiente y rápida de los resultados, algo que no es posible con el algoritmo AKS.

La prueba de primalidad AKS se basa en el siguiente teorema: Dado un entero${\displaystyle n\geq 2}$y entero${\displaystyle a}$coprimo a${\displaystyle n}$,${\displaystyle n}$es primo si y solo si la relación de congruencia polinómica

se mantiene dentro del anillo polinomial${\displaystyle (\mathbb {Z} /n\mathbb {Z} )[X]}$. ^{[ 1 ]} Tenga en cuenta que${\displaystyle X}$denota la indeterminada que genera este anillo de polinomios.

Este teorema es una generalización a polinomios del pequeño teorema de Fermat . En una dirección, se puede demostrar fácilmente utilizando el teorema del binomio junto con la siguiente propiedad del coeficiente binomial :

${\displaystyle {n \choose k}\equiv 0{\pmod {n}}}$a pesar de${\displaystyle 0<k<n}$si${\displaystyle n}$es primordial.

Si bien la relación ( 1 ) constituye una prueba de primalidad en sí misma, verificarla requiere un tiempo exponencial : el enfoque de fuerza bruta requeriría la expansión de la${\displaystyle (X+a)^{n}}$polinomio y una reducción${\displaystyle {\pmod {n}}}$del resultado${\displaystyle n+1}$coeficientes.

La congruencia es una igualdad en el anillo de polinomios.${\displaystyle (\mathbb {Z} /n\mathbb {Z} )[X]}$. Evaluar en un anillo cociente de${\displaystyle (\mathbb {Z} /n\mathbb {Z} )[X]}$crea un límite superior para el grado de los polinomios involucrados. El AKS evalúa la igualdad en${\displaystyle (\mathbb {Z} /n\mathbb {Z} )[X]/(X^{r}-1)}$, haciendo que la complejidad computacional dependa del tamaño de${\displaystyle r}$. Para mayor claridad, ^{[ 1 ]} esto se expresa como la congruencia

lo cual es lo mismo que:

para algunos polinomios${\displaystyle f}$y${\displaystyle g}$.

Tenga en cuenta que todos los números primos satisfacen esta relación (eligiendo${\displaystyle g=0}$en ( 3 ) da ( 1 ), que se cumple para${\displaystyle n}$primo). Esta congruencia se puede comprobar en tiempo polinomial cuando${\displaystyle r}$es polinomial a los dígitos de${\displaystyle n}$El algoritmo AKS evalúa esta congruencia para un gran conjunto de${\displaystyle a}$valores, cuyo tamaño es polinómico a los dígitos de${\displaystyle n}$. La prueba de validez del algoritmo AKS muestra que se puede encontrar un${\displaystyle r}$y un conjunto de${\displaystyle a}$valores con las propiedades anteriores tales que si se cumplen las congruencias entonces${\displaystyle n}$es una potencia de un número primo. ^{[ 1 ]}

En la primera versión del artículo citado anteriormente, los autores demostraron que la complejidad temporal asintótica del algoritmo es${\displaystyle {\tilde {O}}(\log(n)^{12})}$(usando Õ de la notación O grande )—la duodécima potencia del número de dígitos en n veces un factor que es polilogarítmico en el número de dígitos. Sin embargo, este límite superior era bastante impreciso; una conjetura ampliamente aceptada sobre la distribución de los primos de Sophie Germain , de ser cierta, reduciría inmediatamente el peor caso a${\displaystyle {\tilde {O}}(\log(n)^{6})}$.

En los meses posteriores al descubrimiento, aparecieron nuevas variantes (Lenstra 2002, Pomerance 2002, Berrizbeitia 2002, Cheng 2003, Bernstein 2003a/b, Lenstra y Pomerance 2003), que mejoraron considerablemente la velocidad de cálculo. Debido a la existencia de tantas variantes, Crandall y Papadopoulos se refieren a la "clase AKS" de algoritmos en su artículo científico "Sobre la implementación de pruebas de primalidad de la clase AKS", publicado en marzo de 2003.

En respuesta a algunas de estas variantes y a otros comentarios, el artículo "PRIMES is in P" se actualizó con una nueva formulación del algoritmo AKS y de su prueba de corrección. (Esta versión se publicó finalmente en Annals of Mathematics ). Si bien la idea básica se mantuvo, r se eligió de una manera nueva y la prueba de corrección se organizó de forma más coherente. La nueva prueba se basó casi exclusivamente en el comportamiento de los polinomios ciclotómicos sobre cuerpos finitos . El nuevo límite superior de la complejidad temporal fue${\displaystyle {\tilde {O}}(\log(n)^{10.5})}$, posteriormente reducido utilizando resultados adicionales de la teoría del tamiz a${\displaystyle {\tilde {O}}(\log(n)^{7.5})}$.

En 2005, Pomerance y Lenstra demostraron una variante de AKS que funciona en${\displaystyle {\tilde {O}}(\log(n)^{6})}$operaciones, ^{[ 3 ]} lo que llevó a otra versión actualizada del artículo. ^{[ 4 ]} Agrawal, Kayal y Saxena propusieron una variante que se ejecutaría en${\displaystyle {\tilde {O}}(\log(n)^{3})}$si la conjetura de Agrawal fuera cierta; sin embargo, un argumento heurístico de Pomerance y Lenstra sugirió que probablemente sea falsa.

El algoritmo es el siguiente: ^{[ 1 ]}

Entrada: entero n  >  1 .

1. Comprueba si n es una potencia perfecta : si n  = a ^b  para enteros a  >  1 y b  >  1 , entonces imprime composite .
2. Encuentra el r más pequeño tal que ord _r ( n )  >  (log ₂ n ) ² . Si r y n no son coprimos, entonces imprime composite .
3. Para todo 2 ≤ a ≤ min ( r , n −1), compruebe que a no divide a n : Si a | n para algún 2 ≤ a ≤ min ( r , n −1), entonces genere composite .
4. Si n ≤ r , entonces imprime primo .
5. Para a  =  1 a${\displaystyle \left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor }$hacer

   si ( X + a ) ⁿ ≠ X ⁿ + a (mod X ^r − 1, n ), entonces generar compuesto ;

6. Salida prima .

Aquí ord _r ( n ) es el orden multiplicativo de n módulo r , log ₂ es el logaritmo binario y${\displaystyle \varphi (r)}$es la función totiente de Euler de r .

El paso 3 se muestra en el artículo como la comprobación de 1 < mcd( a , n ) < n para todo a ≤ r . Se puede observar que esto es equivalente a la división por tanteo hasta r , que se puede realizar de forma muy eficiente sin utilizar mcd . De manera similar, la comparación del paso 4 se puede reemplazar haciendo que la división por tanteo devuelva un número primo una vez que haya comprobado todos los valores hasta e incluyendo${\displaystyle \left\lfloor {\sqrt {n}}\right\rfloor .}$

Una vez que las entradas son muy pequeñas, el paso 5 domina el tiempo empleado. La reducción esencial de la complejidad (de exponencial a polinómica) se logra realizando todos los cálculos en el anillo finito.

${\displaystyle R=(\mathbb {Z} /n\mathbb {Z} )[X]/(X^{r}-1)}$

compuesto de${\displaystyle n^{r}}$elementos. Este anillo contiene únicamente los${\displaystyle r}$monomios${\displaystyle \{X^{0},X^{1},\ldots ,X^{r-1}\}}$y los coeficientes están en${\displaystyle \mathbb {Z} /n\mathbb {Z} }$que tiene${\displaystyle n}$elementos, todos ellos codificables dentro${\displaystyle \log _{2}(n)}$bits.

La mayoría de las mejoras posteriores realizadas al algoritmo se han concentrado en reducir el tamaño de r, lo que hace que la operación central en el paso 5 sea más rápida, y en reducir el tamaño de s , el número de bucles realizados en el paso 5. ^{[ 5 ]} Por lo general, estos cambios no modifican la complejidad computacional, pero pueden conducir a una reducción de muchos órdenes de magnitud en el tiempo empleado; por ejemplo, la versión final de Bernstein tiene una aceleración teórica de un factor de más de 2 millones.

Entrada : entero n = 31 > 1. (* Paso 1 *) Si ( n = a b para enteros a > 1 y b > 1), imprime compuesto . Para ( b = 2; b <= log 2 (n); b++) { a = n 1/b ; Si (a es un entero), Devuelve [Compuesto] } a = n 1/2 ...n 1/4 = {5.568, 3.141, 2.360} (* Paso 2 *) Encuentra el r más pequeño tal que O r ( n ) > (log 2 n ) 2 . maxk = ⌊(log 2 n) 2 ⌋; maxr = Max[3, ⌈(Log 2 n) 5 ⌉]; (* maxr realmente no es necesario *) nextR = Verdadero; Para (r = 2; nextR && r < maxr; r++) { nextR = Falso; Para (k = 1; (!nextR) && k ≤ maxk; k++) { nextR = (Mod[n k , r] == 1 || Mod[n k , r]==0) } } r--; (*el bucle se incrementa en uno*) r = 29 (* Paso 3 *) Si (1 < mcd ( a , n ) < n para algún a ≤ r ), imprimir compuesto . Para (a = r; a > 1; a--) { Si ((mcd = MCD[a,n]) > 1 && mcd < n), Devolver [Compuesto] } mcd = {MCD(29,31)=1, MCD(28,31)=1, ..., MCD(2,31)=1} ≯ 1 (* Paso 4 *) Si ( n ≤ r ), imprime prime . Si (n ≤ r), devuelve [Prime] (* este paso puede omitirse si n > 5690034 *) 31 > 29 (* Paso 5 *) Para a = 1 a${\displaystyle \left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor }$hacer Si (( X + a ) n ≠ X n + a (mod X r − 1, n )), generar compuesto ; φ[x_] := EulerPhi[x]; PolyModulo[f_] := PolynomialMod[ PolynomialRemainder [f, x r -1, x], n]; max = Piso[Log[2, n] √ φ[r] ]; Para (a = 1; a ≤ max; a++) { Si (PolyModulo[(x+a) n - PolynomialRemainder[x n +a, x r -1, x]] ≠ 0) { Devolver [Composite] { } (x+a) 31 = a 31 +31a 30 x +465a 29 x 2 +4495a 28 x 3 +31465a 27 x 4 +169911a 26 x 5 +736281a 25 x 6 +2629575a 24 x 7 +7888725a 23 x 8 +20160075a 22 x 9 +44352165a 21 x 10 +84672315a 20 x 11 +141120525a 19 x 12 +206253075a 18 x 13 +265182525a 17 x 14 +300540195a 16 x 15 +300540195a 15 x 16 +265182525a 14 x 17 +206253075a 13 x 18 +141120525a 12 x 19 +84672315a 11 x 20 +44352165a 10 x 21 +20160075a 9 x 22 +7888725a 8 x 23 +2629575a 7 x 24 +736281a 6 x 25 +169911a 5 x 26 +31465a 4 x 27 +4495a 3 x 28 +465a 2 x 29 +31ax 30 +x 31 Resto del polinomio [(x+a) 31 , x 29 -1] = 465a 2 +a 31 +(31a+31a 30 )x +(1+465a 29 )x 2 +4495a 28 x 3 +31465a 27 x 4 +169911a 26 x 5 +736281a 25 x 6 +2629575a 24 x 7 +7888725a 23 x 8 +20160075a 22 x 9 +44352165a 21 x 10 +84672315a 20 x 11 +141120525a 19 x 12 +206253075a 18 x 13 +265182525a 17 x 14 +300540195a 16 x 15 +300540195a 15 x 16 +265182525a 14 x 17 +206253075a 13 x 18 +141120525a 12 x 19 +84672315a 11 x 20 +44352165a 10 x 21 +20160075a 9 x 22 +7888725a 8 x 23 +2629575a 7 x 24 +736281a 6 x 25 +169911a 5 x 26 +31465a 4 x 27 +4495a 3 x 28 ( A ) PolinomioMod [PolynomialRemainder [(x+a) 31 , x 29 -1], 31] = a 31 +x 2 ( B ) Resto del polinomio [x 31 +a, x 29 -1] = a+x 2 ( A ) - ( B ) = a 31 +x 2 - (a+x 2 ) = a 31 -a ${\displaystyle \max =\left\lfloor \log _{2}(31){\sqrt {\varphi (29)}}\right\rfloor =26}$ {1 31 -1 = 0 (mod 31), 2 31 -2 = 0 (mod 31), 3 31 -3 = 0 (mod 31), ..., 26 31 -26 = 0 (mod 31)} (* Paso 6 *) Salida prime . 31 Debe ser Prime

• Dietzfelbinger, Martin (2004). Pruebas de primalidad en tiempo polinomial. De algoritmos aleatorios a PRIMES está en PNotas de clase en Ciencias de la Computación. Vol.  3000. Berlín: Springer-Verlag . ISBN 3-540-40344-2. Zbl 1058.11070 . 

• Weisstein, Eric W. "Prueba de primalidad AKS" . MathWorld .
• R. Crandall, Apple ACG y J. Papadopoulos (18 de marzo de 2003): Sobre la implementación de pruebas de primalidad de clase AKS (PDF)
• Artículo de Bornemann, que incluye fotos e información sobre los tres científicos indios (PDF).
• Andrew Granville: Es fácil determinar si un número entero dado es primo.
• Los hechos fundamentales: De Euclides a AKS , por Scott Aaronson (PDF)
• Los PRIMOS están en P pequeñas preguntas frecuentes de Anton Stiglic
• Mención del Premio Gödel 2006
• Mención del Premio Fulkerson 2006
• Recurso del algoritmo AKS "PRIMES in P"