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 está en P". [1] El algoritmo fue el primero que puede determinar de manera comprobable si un número dado es primo o compuesto dentro del tiempo polinomial , sin depender de lahipótesis generalizada de Riemann , o cualquier conjetura matemática . La prueba también se destaca por no apoyarse en el campo de análisis . [2] Los autores recibieron el Premio Gödel 2006 y el Premio Fulkerson 2006 por este trabajo.
Importancia
AKS es el primer algoritmo de prueba de primalidad que es simultáneamente general , polinomial , determinista e incondicional . Los algoritmos anteriores se habían desarrollado durante siglos y lograban tres de estas propiedades como máximo, pero no las cuatro.
- El algoritmo AKS se puede utilizar para verificar la primacía 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 solo funciona con números de Mersenne , mientras que la prueba de Pépin solo se puede aplicar a números de Fermat .
- El tiempo máximo de ejecución del algoritmo se puede expresar como un polinomio sobre el número de dígitos del número objetivo. 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 distingue de forma determinista si el número objetivo es primo o compuesto. Las pruebas aleatorias, como Miller-Rabin y Baillie-PSW , pueden probar cualquier número dado para determinar la primacía en el tiempo polinomial, pero se sabe que solo producen un resultado probabilístico.
- La exactitud de AKS no está condicionada a ninguna hipótesis subsidiaria no probada . En contraste, la versión de Miller de la prueba de 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 es de inmensa importancia teórica, no se utiliza en la práctica, lo que lo convierte en un algoritmo galáctico . Para entradas de 64 bits, la prueba de primalidad 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 una verificación independiente y rápida de los resultados, lo que no es posible con el algoritmo AKS.
Conceptos
La prueba de primalidad de AKS se basa en el siguiente teorema: Dado un número entero y entero coprime a, es primo si y solo si la relación de congruencia polinomial
( 1 )
sostiene. [1] Tenga en cuenta que debe entenderse como un símbolo formal.
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 todos Si es primordial.
Si bien la relación ( 1 ) constituye una prueba de primordialidad en sí misma, verificarla toma un tiempo exponencial : el enfoque de fuerza bruta requeriría la expansión de la polinomio y una reducción de la resultante coeficientes.
La congruencia es una igualdad en el anillo polinomial . Evaluando en un anillo cociente decrea un límite superior para el grado de los polinomios involucrados. El AKS evalúa la igualdad en, haciendo que la complejidad computacional dependa del tamaño de. Para mayor claridad, [1] esto se expresa como la congruencia
( 2 )
que es lo mismo que:
( 3 )
para algunos polinomios y .
Tenga en cuenta que todos los primos satisfacen esta relación (eligiendo en ( 3 ) da ( 1 ), que se cumple paraprincipal). Esta congruencia se puede verificar en tiempo polinomial cuando es polinomio a los dígitos de . El algoritmo AKS evalúa esta congruencia para un gran conjunto de valores, cuyo tamaño es polinomial a 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 de modo que si las congruencias se mantienen entonces es un poder de primo. [1]
Historia y tiempo de ejecució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 grande ): 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 estaba bastante suelto; una conjetura ampliamente aceptada sobre la distribución de los números primos de Sophie Germain , de ser cierta, inmediatamente reduciría 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 "Sobre la implementación de las 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 está en 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 manera nueva 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 campos finitos . El nuevo límite superior de la complejidad del tiempo fue, luego se redujo utilizando resultados adicionales de la teoría del tamiz para.
En 2005, Pomerance y Lenstra demostraron una variante de AKS que se ejecuta enoperaciones, [3] dando lugar a otra versión actualizada del documento. [4] Agrawal, Kayal y Saxena propusieron una variante que se ejecutaría ensi la conjetura de Agrawal fuera cierta; sin embargo, un argumento heurístico de Pomerance y Lenstra sugirió que probablemente sea falso. [1]
El algoritmo
El algoritmo es el siguiente: [1]
- Entrada: entero n > 1 .
- Comprobar si n es un poder perfecto : si n = un B para los números enteros a > 1 y b > 1 , la salida compuesta .
- Encuentre el r más pequeño tal que ord r ( n )> (log 2 n ) 2 . (si r y n no son primos entre sí, y luego omitir este r )
- Para todo 2 ≤ a ≤ min ( r , n −1), compruebe que a no divide n : Si a | n para algunos 2 ≤ a ≤ min ( r , n −1), compuesto de salida .
- Si n ≤ r , la salida es primo .
- Para a = 1 a hacer
- if ( X + a ) n ≠ X n + a (mod X r - 1, n ), compuesto de salida ;
- Salida principal .
Aquí ord r ( n ) es el orden multiplicativo de n módulo r , log 2 es el logaritmo binario yes la función totient de Euler de r .
El paso 3 se muestra en el documento como una verificación de 1 <( a , n ) < n para todo 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 gcd . 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 verificado todos los valores hasta e incluyendo
Una vez más allá de las entradas muy pequeñas, el paso 5 domina el tiempo necesario. La reducción esencial de la complejidad (de exponencial a polinomio) se logra realizando todos los cálculos en el anillo finito.
que consiste en elementos. Este anillo contiene solo el monomios , y los coeficientes están en que tiene elementos todos ellos codificables dentro bits.
La mayoría de las mejoras posteriores realizadas al algoritmo se han concentrado en reducir el tamaño de r, lo que acelera la operación del núcleo en el paso 5, y en reducir el tamaño de s , el número de bucles realizados en el paso 5. [5] Normalmente, estos cambios no cambiar la complejidad computacional, pero puede llevar a muchos órdenes de magnitud menos tiempo, por ejemplo, la versión final de Bernstein tiene una aceleración teórica por 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 . Paso 5 también es correcta: ya que (2) es cierto para cualquier elección de un primos entre sí a n y r si n es primo, un medio de desigualdad que n deben ser de material compuesto.
El caso difícil del algoritmo es la declaración iterada en el paso 5. Si esto dentro del anillo finito R resulta en la incongruencia
esto es equivalente a
- ,
de modo que después de reducir a los monomios r mediante solo tiene que ser revisado. [1]
Ejemplo 1: n = 31 es primo
- Entrada: número entero n = 31> 1.
Si n = a b para enteros a > 1 y b > 1, salida compuesta . Para [b = 2, b <= log 2 (n), b ++, a = n 1 / b ; Si [a es un número entero, devuelve [Compuesto]] ]; a = n 1/2 ... n 1/4 = {5.568, 3.141, 2.360}
Encuentre 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
,> 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 Si 1 < mcd ( a , n ) < n para algún a ≤ r , salida compuesta . Para [a = r, a> 1, a--, Si [(gcd = GCD [a, n])> 1 && gcd
,> ]; mcd = {MCD (29,31) = 1, MCD (28,31) = 1, ..., MCD (2,31) = 1} ≯ 1 Si n ≤ r , la salida es primo . Si [n ≤ r, devuelve [Prime]]; (* este paso puede omitirse si n> 5690034 *) 31> 29
Para a = 1 a hacer if ( X + a ) n ≠ X n + a (mod X r - 1, n ), compuesto de salida ; φ [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 [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 Polinomio Resto [(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 ) PolynomialMod [PolynomialRemainder [(x + a) 31 , x 29 -1], 31] = a 31 + x 2 ( B ) Polinomio Resto [x 31 + a, x 29 -1] = a + x 2 ( A ) - ( B ) = a 31 + x 2 - (a + x 2 ) = a 31 -a max = = 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)}
Salida principal . 31 Debe ser Prime
Donde PolynomialMod es una reducción de módulo de términos del polinomio. por ejemplo, PolynomialMod [x + 2x 2 + 3x 3 , 3] = x + 2x 2 + 0x 3
[6]
Referencias
- ^ a b c d e f g Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004). "PRIMES está en P" (PDF) . Annals of Mathematics . 160 (2): 781–793. doi : 10.4007 / annals.2004.160.781 . JSTOR 3597229 .
- ^ Granville, Andrew (2005). "Es fácil determinar si un número entero dado es primo" . Toro. Amer. Matemáticas. Soc . 42 : 3-38. doi : 10.1090 / S0273-0979-04-01037-7 .
- ^ HW Lenstra Jr. y Carl Pomerance, " Prueba de primordialidad con períodos gaussianos ", versión preliminar 20 de julio de 2005.
- ^ HW Lenstra jr. y Carl Pomerance, " Pruebas de primordialidad con períodos gaussianos. Archivado el 25 de febrero de 2012en la Wayback Machine ", versión del 12 de abril de 2011.
- ^ Daniel J. Bernstein, " Proving Primality After Agrawal-Kayal-Saxena ", versión del 25 de enero de 2003.
- ^ Consulte lapágina de AKS Talk para ver una discusión sobre por qué falta el 'Ejemplo 2: n no es Prime después del Paso 4'.
Otras lecturas
- Dietzfelbinger, Martin (2004). Prueba de primalidad en tiempo polinomial. A partir de algoritmos aleatorios a Primes está en P . Apuntes de conferencias en informática. 3000 . Berlín: Springer-Verlag . ISBN 3-540-40344-2. Zbl 1058.11070 .
enlaces externos
- Weisstein, Eric W. "Prueba de primordialidad AKS" . MathWorld .
- R. Crandall, Apple ACG y J. Papadopoulos (18 de marzo de 2003): Sobre la implementación de las pruebas de primalidad de la clase AKS (PDF)
- Artículo de Borneman, que contiene fotos e información sobre los tres científicos indios (PDF)
- Andrew Granville: Es fácil determinar si un entero dado es primo
- Los hechos principales: de Euclides a AKS , por Scott Aaronson (PDF)
- PRIMES está en P pequeñas preguntas frecuentes de Anton Stiglic
- Cita del Premio Gödel 2006
- Cita del premio Fulkerson 2006
- El recurso del algoritmo AKS "PRIMES in P"
- Grime, Dr. James. "Prueba infalible para los Primes - Numberphile" (video) . Brady Haran . [el video describe la relación de tiempo exponencial (1), a la que llama AKS]