stringtranslate.com

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.

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

se cumple dentro del anillo polinomial . [1] Nótese que denota lo indeterminado que genera este anillo polinomial.

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 :

para todo si es primo.

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 .

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

que es lo mismo que:

para algunos polinomios y .

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]

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 .

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 .

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.

El algoritmo

El algoritmo es el siguiente: [1]

Entrada: entero n  > 1 .
  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 .
  2. 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 .
  3. 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 .
  4. Si nr , entonces la salida es primo .
  5. Para a  = 1 hacer
    si ( X + a ) nX n + a (mod X r − 1, n ), entonces salida compuesta ;
  6. Salida principal .

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

El paso 3 se muestra en el documento como la comprobación de 1 < ( a , n ) < n para todos los ar . 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

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.

compuesto de elementos. Este anillo contiene únicamente los monomios y los coeficientes están en el que tiene elementos, todos ellos codificables en 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 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]

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 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 . máxk = ⌊(log 2 n) 2 ⌋; maxr = Max[3, ⌈(Log 2 n) 5 ⌉]; (*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 ar ), 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 ( nr ), 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 ) nX n + a (mod X r  1, n )), salida compuesta ;     φ[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) n - PolynomialRemainder[x n +a, x r -1], x] ≠ 0) { Devolver [Compuesto] { }  (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 polinomial [(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 ) PolinomioMódulo [RestoPolinomial[(x+a) 31 , x 29 -1], 31] = a 31 +x 2  ( B ) Resto polinomial [x 31 + a, x 29 -1] = a+x 2  ( A ) - ( B ) = a 31 + x 2 - (a+x 2 ) = a 31 -a    {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  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 2 +3x 3 , 3] = x+2x 2 +0x 3

[6]

Referencias

  1. ^ 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.
  2. ^ 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 .
  3. ^ HW Lenstra Jr. y Carl Pomerance, "Pruebas de primalidad con períodos gaussianos", versión preliminar 20 de julio de 2005.
  4. ^ 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.
  5. ^ Daniel J. Bernstein, "Demostrar la primalidad después de Agrawal-Kayal-Saxena", versión del 25 de enero de 2003.
  6. ^ 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

Enlaces externos