Prueba de primalidad AKS

La prueba de primalidad AKS (también conocida como prueba de primalidad Agrawal–Kayal–Saxena y prueba ciclotómica AKS ) es un algoritmo determinista de demostración 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 y esto sin depender de conjeturas matemáticas como la hipótesis generalizada de Riemann . La prueba también es notable por no depender del campo de análisis . ^[2] En 2006, los autores recibieron el Premio Gödel y el Premio Fulkerson por su trabajo.

Importancia

AKS es el primer algoritmo de demostración de primalidad que es a la vez general , polinomial , determinista e incondicionalmente correcto . Los algoritmos anteriores se habían desarrollado durante siglos y conseguían tres de estas propiedades como máximo, pero no las cuatro.

El algoritmo AKS se puede utilizar para verificar la primalidad de cualquier número general dado. Se conocen muchas pruebas rápidas de primalidad 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 limitarse mediante un polinomio sobre la cantidad de dígitos del número de destino. ECPP y APR prueban o refutan de manera concluyente que un número dado es primo, pero no se sabe que tengan límites de tiempo polinomiales para todas las entradas.
Se garantiza que el algoritmo distinguirá de manera determinista si el número objetivo es primo o compuesto. Las pruebas aleatorias, como Miller–Rabin y Baillie–PSW , pueden probar la primalidad de cualquier número dado en tiempo polinomial, pero se sabe que solo producen un resultado probabilístico.
La exactitud de AKS no depende de ninguna hipótesis subsidiaria no probada . Por el contrario, la versión de Miller de la prueba Miller-Rabin es completamente determinista y se ejecuta en tiempo polinomial sobre todas las entradas, pero su exactitud depende de la verdad de la hipótesis de Riemann generalizada 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 galáctico . Para entradas de 64 bits, la prueba Baillie–PSW es determinista y se ejecuta muchos órdenes de magnitud más rápido. Para entradas más grandes, el rendimiento de las pruebas ECPP y APR (también incondicionalmente correctas) es muy superior al de AKS. Además, ECPP puede generar un certificado de primalidad que permite la verificación independiente y rápida de los resultados, lo que no es posible con el algoritmo AKS.

Conceptos

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

se cumple dentro del anillo polinomial . ^[1] Nótese que denota lo indeterminado que genera este anillo polinomial. $(\mathbb {Z} /n\mathbb {Z} )[X]$ ${\estilo de visualización X}$

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 :

{n \elija k}\equiv 0{\pmod {n}}

para todo si es primo.

{\estilo de visualización 0<k<n}

{\estilo de visualización n}

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 del polinomio y una reducción de los coeficientes resultantes . $(X+a)^{n}$ ${\pmod {n}}$ ${\estilo de visualización n+1}$

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

que es lo mismo que:

para algunos polinomios y . ${\estilo de visualización f}$ ${\estilo de visualización g}$

Nótese que todos los primos satisfacen esta relación (eligiendo en ( 3 ) se obtiene ( 1 ), que es válida para los primos). Esta congruencia se puede comprobar en tiempo polinomial cuando es polinomial con los dígitos de . El algoritmo AKS evalúa esta congruencia para un conjunto grande de valores, cuyo tamaño es polinomial con los dígitos de . La prueba de validez del algoritmo AKS muestra que se puede encontrar un y un conjunto de valores con las propiedades anteriores tales que si se cumplen las congruencias entonces es una potencia de un primo. ^[1] ${\estilo de visualización g=0}$ ${\estilo de visualización n}$ ${\estilo de visualización r}$ ${\estilo de visualización n}$ ${\estilo de visualización a}$ ${\estilo de visualización n}$ ${\estilo de visualización r}$ ${\estilo de visualización a}$ ${\estilo de visualización n}$

Historia y duración

En la primera versión del artículo citado anteriormente, los autores demostraron que la complejidad temporal asintótica del algoritmo es (usando Õ de la notación O mayúscula ) la duodécima potencia del número de dígitos en n multiplicado por 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 de los casos a . ${\tilde {O}}(\log(n)^{12})$ ${\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 enormemente la velocidad de cálculo. Debido a la existencia de muchas variantes, Crandall y Papadopoulos se refieren a la "clase AKS" de algoritmos en su artículo científico "On the implementation of AKS-class primality tests", 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 siguió siendo la misma, se eligió r de una nueva manera y la prueba de corrección se organizó de manera más coherente. La nueva prueba se basó casi exclusivamente en el comportamiento de polinomios ciclotómicos sobre cuerpos finitos . El nuevo límite superior de la complejidad temporal fue , que luego se redujo utilizando resultados adicionales de la teoría de tamices a . ${\tilde {O}}(\log(n)^{10.5})$ ${\tilde {O}}(\log(n)^{7.5})$

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

El algoritmo

El algoritmo es el siguiente: ^[1]

Entrada: entero

n > 1

Compruebe si n es una potencia perfecta : si $n = a b$ para números enteros $a > 1$ y $b > 1$ , entonces obtenga como salida un compuesto .
Encuentra el r más pequeño tal que $ord r (n) > (log 2 n) 2$ . Si r y n no son coprimos, entonces el resultado es compuesto .
Para todos los 2 ≤ a ≤ min ( r , n −1), verifique que a no divide a n : Si a | n para algunos 2 ≤ a ≤ min ( r , n −1), entonces obtenga como salida composite .
Si n ≤ r , entonces la salida es primo .
Para $a =$ 1 hacer $\left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor$
si ( X + a ) ⁿ ≠ X ⁿ + a (mod X ^r − 1, n ), entonces salida compuesta ;
Salida principal .

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

El paso 3 se muestra en el documento como la comprobación de 1 < ( a , n ) < n para todos los a ≤ r . Se puede ver que esto es equivalente a la división de prueba hasta r , que se puede hacer de manera muy eficiente sin usar mcd . De manera similar, la comparación en el paso 4 se puede reemplazar haciendo que la división de prueba devuelva primo una vez que haya comprobado todos los valores hasta e incluyendo $\left\lfloor {\sqrt {n}}\right\rfloor .$

Una vez superadas las entradas 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.

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

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

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 principal en el paso 5 sea más rápida, y en reducir el tamaño de s , la cantidad de bucles realizados en el paso 5. ^[5] Normalmente, estos cambios no cambian la complejidad computacional, pero pueden llevar a muchos órdenes de magnitud menos de tiempo; por ejemplo, la versión final de Bernstein tiene una aceleración teórica de un factor de más de 2 millones.

Esquema de prueba de validez

Para que el algoritmo sea correcto, todos los pasos que identifican n deben ser correctos. Los pasos 1, 3 y 4 son trivialmente correctos, ya que se basan en pruebas directas de la divisibilidad de n . El paso 5 también es correcto: dado que (2) es cierto para cualquier elección de un coprimo de n y r si n es primo, una desigualdad significa que n debe ser compuesto.

La parte difícil de la prueba es demostrar que el paso 6 es verdadero. Su prueba de corrección se basa en los límites superior e inferior de un grupo multiplicativo en construido a partir de los binomios ( X + a ) que se prueban en el paso 5. El paso 4 garantiza que estos binomios son elementos distintos de . Para la elección particular de r , los límites producen una contradicción a menos que n sea primo o una potencia de un primo. Junto con la prueba del paso 1, esto implica que n siempre es primo en el paso 6. ^[1] $\mathbb {Z} _ {n}[x]$ $\left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor$ $\mathbb {Z} _ {n}[x]$

Ejemplo 1:norte= 31 es primo

 Entrada : entero n = 31 > 1. (* Paso 1 *)  Si ( n = a ^b para los enteros a > 1 y b > 1), salida  compuesta . Para ( b = 2; b <= log ₂ (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 ₂  n ) ² . máxk = ⌊(log ₂ n) ² ⌋; maxr = Max[3, ⌈(Log ₂ n) ⁵ ⌉]; (*maxr realmente no es necesario*) nextR = Verdadero; Para (r = 2; siguienteR y r < máxr; r++) { siguienteR = Falso; Para (k = 1; (!nextR) && k ≤ maxk; k++) { siguienteR = (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 ), salida  compuesta . Para (a = r; a > 1; a--) { Si ((mcd = MCD[a,n]) > 1 && mcd < n), Devuelve [Compuesta] }  mcd = {MCD(29,31)=1, MCD(28,31)=1, ..., MCD(2,31)=1} ≯ 1 (*Paso 4*)  Si ( n ≤ r ), salida  prime . Si (n ≤ r), devuelve [Prime] (*este paso puede omitirse si n > 5690034*)  31 > 29  (*Paso 5*)  Para  a = 1 hacer  Si (( X + a ) ⁿ ≠ X ⁿ + a (mod X r − 1, n )), ^salida compuesta ; $\left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor$      φ[x_] := EulerPhi[x]; PolyModulo[f_] := PolynomialMod[ PolynomialRemainder [f, x ^r -1, x], n]; máx = Floor[Log[2, n] √ φ[r] ]; Para (a = 1; a ≤ máx; a++) { Si (PolyModulo[(x+a) ⁿ - PolynomialRemainder[x ⁿ +a, x ^r -1], x] ≠ 0) { Devolver [Compuesto] { }  (x+a) ³¹ = a ³¹ + 31a ³⁰ x + 465a ²⁹ x ² + 4495a ²⁸ x ³ + 31465a ²⁷ x ⁴ + 169911a ²⁶ x ⁵ + 736281a ²⁵ x ⁶ + 2629575a ²⁴ x ⁷ + 7888725a ²³ x ⁸ + 20160075a ²² x ⁹ + 44352165a ²¹ x ¹⁰ + 84672315a ²⁰ x ¹¹ + 141120525a ¹⁹ x ¹² + 206253075a ¹⁸ x ¹³ + 265182525a ¹⁷ x ¹⁴ + 300540195a ¹⁶ x ¹⁵ + 300540195a ¹⁵ x ¹⁶ + 265182525a ¹⁴ x ¹⁷ + 206253075a ¹³ x ¹⁸ + 141120525a ¹² x ¹⁹ + 84672315a ¹¹ x ²⁰ + 44352165a ¹⁰ x ²¹ + 20160075a ⁹ x ²² + 7888725a ⁸ x ²³ + 2629575a ⁷ x ²⁴ + 736281a ⁶ x ²⁵ + 169911a ⁵ x ²⁶ + 31465a ⁴ x ²⁷ + 4495a ³ x ²⁸ + 465a ² x ²⁹ + 31ax ³⁰ + x ³¹  Resto polinomial [(x+a) ³¹ , x ²⁹ -1] = 465a ² + a ³¹ + (31a + 31a ³⁰ ) x + (1 + 465a ²⁹ ) x ² + 4495a ²⁸ x ³ + 31465a ²⁷ x ⁴ + 169911a ²⁶ x ⁵ + 736281a ²⁵ x ⁶ + 2629575a ²⁴ x ⁷ + 7888725a ²³ x ⁸ + 20160075a ²² x ⁹ + 44352165a ²¹ x ¹⁰ + 84672315a ²⁰ x ¹¹ + 141120525a ¹⁹ x ¹² + 206253075a ¹⁸ x ¹³ + 265182525a ¹⁷ x ¹⁴ + 300540195a ¹⁶ x ¹⁵ +300540195a ¹⁵ x ¹⁶ +265182525a ¹⁴ x ¹⁷ +206253075a ¹³ x ¹⁸ +141120525a ¹² x ¹⁹ +84672315a ¹¹ x ²⁰ +44352165a ¹⁰ x ²¹ +20160075a ⁹ x ²² +7888725a ⁸ x ²³ +2629575a ⁷ x ²⁴ +736281a ⁶ x ²⁵ +169911a ⁵ x ²⁶ +31465a ⁴ x ²⁷ +4495a ³ x ²⁸  ( A ) PolinomioMódulo [RestoPolinomial[(x+a) ³¹ , x ²⁹ -1], 31] = a ³¹ +x ²  ( B ) Resto polinomial [x ³¹ + a, x ²⁹ -1] = a+x ²  ( A ) - ( B ) = a ³¹ + x ² - (a+x ² ) = a ³¹ -a   $\max =\left\lfloor \log _{2}(31){\sqrt {\varphi (29)}}\right\rfloor =26$   {1 ³¹ -1 = 0 (mod 31), 2 ³¹ -2 = 0 (mod 31), 3 ³¹ -3 = 0 (mod 31), ..., 26 ³¹ -26 = 0 (mod 31)}  (*Paso 6*)  Salida  principal . 31 Debe ser Prime

Donde PolynomialMod es una reducción módulo término por término del polinomio. p. ej. PolynomialMod[x+2x ² +3x ³ , 3] = x+2x ² +0x ³

^[6]

Referencias

^ abcdef Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004). "PRIMES está en P" (PDF) . Anales de Matemáticas . 160 (2): 781–793. doi : 10.4007/anales.2004.160.781 . JSTOR 3597229.
^ Granville, Andrew (2005). "Es fácil determinar si un número entero dado es primo". Bull. Amer. Math. Soc . 42 : 3–38. doi : 10.1090/S0273-0979-04-01037-7 .
^ HW Lenstra Jr. y Carl Pomerance, "Pruebas de primalidad con períodos gaussianos", versión preliminar 20 de julio de 2005.
^ HW Lenstra Jr. y Carl Pomerance, "Pruebas de primalidad con períodos gaussianos Archivado el 25 de febrero de 2012 en Wayback Machine ", versión del 12 de abril de 2011.
^ Daniel J. Bernstein, "Demostrar la primalidad después de Agrawal-Kayal-Saxena", versión del 25 de enero de 2003.
^ Consulte la página de discusión de AKS para ver un debate sobre por qué falta 'Ejemplo 2: n no es primo después del paso 4'.

Lectura adicional

Dietzfelbinger, Martin (2004). Pruebas de primalidad en tiempo polinomial. De algoritmos aleatorios a PRIMES está en P. Apuntes de clases sobre informática. Vol. 3000. Berlín: Springer-Verlag . ISBN 3-540-40344-2.Zbl 1058.11070 .

Enlaces externos

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 la clase AKS (PDF)
Artículo de Borneman, que contiene fotografías 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 principales: desde Euclides hasta AKS, por Scott Aaronson (PDF)
Preguntas frecuentes sobre PRIMES en P, de Anton Stiglic
Mención del Premio Gödel 2006
Mención del Premio Fulkerson 2006
Recurso del algoritmo "PRIMES in P" de AKS