¿Cuándo es la prueba de primitiva AKS realmente más rápida que otras pruebas?

Estoy tratando de tener una idea de cómo se debe interpretar la prueba de primalidad AKS a medida que la conozco, por ejemplo, un corolario para demostrar que PRIMES ⊆ P, o un algoritmo realmente práctico para pruebas de primalidad en computadoras.

La prueba tiene tiempo de ejecución polinómico pero con alto grado y posibles constantes altas. Entonces, en la práctica, ¿en qué supera otras pruebas de primalidad? Aquí, es el número de dígitos de la prima, y ​​"superar" se refiere al tiempo de ejecución aproximado de las pruebas en arquitecturas informáticas típicas.$n$$n$

Estoy interesado en algoritmos funcionalmente comparables, es decir, deterministas que no necesitan conjeturas para la corrección.

Además, ¿es práctico usar tal prueba sobre las otras, dados los requisitos de memoria de la prueba?

Respuesta rápida: nunca, para fines prácticos. Actualmente no tiene ningún uso práctico.

Primero, separemos las pruebas de composición "prácticas" de las pruebas de primalidad. El primero es lo suficientemente bueno para casi todos los propósitos, aunque existen diferentes niveles de pruebas que las personas consideran adecuadas. Para números menores de 2 ^ 64, no se requieren más de 7 pruebas de Miller-Rabin, o una prueba BPSW para una respuesta determinista. Esto será mucho más rápido que AKS y será igual de correcto en todos los casos. Para números superiores a 2 ^ 64, BPSW es ​​una buena opción, con algunas pruebas adicionales de base aleatoria de Miller-Rabin que agregan algo de confianza adicional a muy bajo costo. Casi todos los métodos de prueba comenzarán (o deberían) con una prueba como esta porque es barata y significa que solo hacemos el trabajo duro en números que casi con certeza son primos.

Pasando a las pruebas. En cada caso, la prueba resultante no requiere conjeturas, por lo que se pueden comparar funcionalmente. El "problema" de APR-CL es que no es del todo polinomial, y el "problema" de ECPP / fastECPP es que puede haber números que tarden más de lo esperado.

En el gráfico, vemos dos implementaciones de AKS de código abierto: la primera es del documento v6, la segunda incluye mejoras de Bernstein y Voloch y una buena heurística r / s de Bornemann. Estos usan la segmentación binaria en GMP para las multiplicaciones polinómicas, por lo que son bastante eficientes, y el uso de memoria no es un problema para los tamaños considerados aquí. Producen bonitas líneas rectas con una pendiente de ~ 6.4 en el gráfico log-log, lo cual es genial. Pero la extrapolación a 1000 dígitos llega en tiempos estimados en cientos de miles a millones de años, en comparación con unos pocos minutos para APR-CL y ECPP. Hay otras optimizaciones que podrían hacerse desde el documento de Bernstein de 2002, pero no creo que esto cambie materialmente la situación (aunque hasta que se implemente, esto no está probado).

Finalmente, AKS supera a la división de prueba. El método del teorema BLS75 5 (por ejemplo, prueba n-1) requiere la factorización parcial de n-1. Esto funciona muy bien en tamaños pequeños, y también cuando tenemos suerte y n-1 es fácil de factorizar, pero eventualmente nos quedaremos atrapados teniendo que factorizar algunos semi-prime grandes. Hay implementaciones más eficientes, pero realmente no escala más allá de los 100 dígitos independientemente. Podemos ver que AKS pasará este método. Entonces, si hizo la pregunta en 1975 (y tenía el algoritmo AKS en ese entonces) podríamos calcular el cruce para saber dónde era el algoritmo más práctico AKS. Pero a fines de la década de 1980, APR-CL y otros métodos ciclotómicos eran la comparación correcta, y para mediados de la década de 1990 tendríamos que incluir ECPP.

Los métodos APR-CL y ECPP son implementaciones de código abierto. Primo (ECPP gratuito pero no de código abierto) será más rápido para tamaños de dígitos más grandes y estoy seguro de que tiene una curva más agradable (todavía no he hecho una nueva evaluación comparativa). APR-CL no es polinomial, pero el exponente tiene un factor que, como alguien dijo "va al infinito pero nunca se ha observado que lo haga". Esto nos lleva a creer que, en teoría, las líneas no se cruzarían para ningún valor de n donde AKS terminaría antes de que nuestro sol se quemara. ECPP es un algoritmo de Las Vegas, ya que cuando obtenemos una respuesta es 100% correcta, esperamos un resultado en conjeturada (ECPP) u$\log \log \log n$$O(\log^{5+\epsilon}(n))$$O(\log^{4+\epsilon}(n))$("fastECPP"), pero puede haber números que tarden más. Entonces, nuestra expectativa es que el AKS estándar siempre será más lento que el ECPP para casi todos los números (ciertamente lo ha demostrado para números de hasta 25k dígitos).

AKS puede tener más mejoras a la espera de ser descubiertas que lo hacen práctico. El artículo de Bernstein Quartic analiza un algoritmo aleatorizado basado en AKS , y el artículo fastECPP de Morain hace referencia a otros métodos no deterministas basados ​​en AKS. Este es un cambio fundamental, pero muestra cómo AKS abrió algunas nuevas áreas de investigación. Sin embargo, casi 10 años después, no he visto a nadie usar este método (ni siquiera ninguna implementación). Él escribe en la introducción, "¿Es el tiempo para el nuevo algoritmo más pequeño que el tiempo para encontrar elíptica- certificados curvos? Mi impresión actual es que la respuesta es no, pero que otros resultados [...] podrían cambiar la respuesta ".$O(\log^{4+\epsilon}(n))$$(\lg n)^{4+o(1)}$$(\lg n)^{4+o(1)}$

Algunos de estos algoritmos se pueden paralelizar o distribuir fácilmente. AKS muy fácilmente (la prueba de cada 's' es independiente). ECPP no es demasiado difícil. No estoy seguro acerca de APR-CL.

Los métodos ECPP y BLS75 producen certificados que se pueden verificar de forma independiente y rápida. Esta es una gran ventaja sobre AKS y APR-CL, donde solo tenemos que confiar en la implementación y la computadora que la produjo.

El algoritmo de prueba de primalidad determinista (asintóticamente) más eficiente se debe a Lenstra y Pomerance , que se ejecuta en el tiempo . Si crees en la hipótesis extendida de Riemann, entonces el algoritmo de Miller se ejecuta en el tiempo . Hay muchos otros algoritmos deterministas de prueba de primalidad, por ejemplo, el artículo de Miller tiene un algoritmo , y otro algoritmo bien conocido es Adleman – Pomerance – Rumley, que se ejecuta en el tiempo .$\tilde{O}(\log^6 n)$$\tilde{O}(\log^4 n)$$\tilde{O}(n^{1/7})$$O(\log n^{O(\log\log\log n)})$

En realidad, nadie usa estos algoritmos, ya que son demasiado lentos. En cambio, se utilizan algoritmos probabilísticos de prueba de primalidad, principalmente Miller – Rabin, que es una modificación del algoritmo de Miller mencionado anteriormente (otro algoritmo importante es Solovay – Strassen). Cada iteración de Miller – Rabin se ejecuta en tiempo , por lo que para una probabilidad de error constante (digamos ), todo el algoritmo se ejecuta en tiempo , que es mucho más rápido que Lenstra – Pomerance.$\tilde{O}(\log^2 n)$$2^{-80}$$\tilde{O}(\log^2 n)$

En todas estas pruebas, la memoria no es un problema.

En su comentario, jbapple plantea la cuestión de decidir qué prueba de primalidad usar en la práctica. Esta es una cuestión de implementación y evaluación comparativa: implemente y optimice algunos algoritmos, y determine experimentalmente cuál es el más rápido en qué rango. Para los curiosos, los codificadores de PARI hicieron exactamente eso, y se les ocurrió una función determinista isprimey una función probabilística ispseudoprime, las cuales se pueden encontrar aquí . La prueba probabilística utilizada es Miller – Rabin. El determinista es BPSW.

Aquí hay más información de Dana Jacobsen :

Pari desde la versión 2.3 utiliza una prueba de primalidad APR-CL para isprime(x), y una prueba principal probable BPSW (con la prueba de Lucas "casi extra fuerte") ispseudoprime(x).

Ellos toman argumentos que cambian el comportamiento:

• isprime(x,0) (predeterminado). Utiliza una combinación (BPSW, Pocklington rápido o BLS75 teorema 5, APR-CL).
• isprime(x,1) Utiliza la prueba de Pocklington-Lehmer (simple ).$n-1$

• isprime(x,2) Utiliza APR-CL.

• ispseudoprime(x,0) (predeterminado). Usa BPSW (MR con base 2, Lucas "casi extra fuerte").

• ispseudoprime(x,k) (para ) Hace MR pruebas con bases aleatorias. El RNG se siembra de manera idéntica en cada ejecución de Pari (por lo que la secuencia es determinista) pero no se reinicia entre llamadas como lo hace GMP (las bases aleatorias de GMP son de hecho las mismas bases en cada llamada, por lo que si está mal una vez, siempre estará mal).$k\geq 1$$k$mpz_is_probab_prime_p(x,k)

Pari 2.1.7 utilizó una configuración mucho peor. isprime(x)fueron solo pruebas de MR (por defecto 10), lo que condujo a cosas divertidas como isprime(9)volver cierto con bastante frecuencia. El uso isprime(x,1)haría una prueba de Pocklington, que estuvo bien durante aproximadamente 80 dígitos y luego se volvió demasiado lenta para ser generalmente útil.

También escribes En realidad, nadie usa estos algoritmos, ya que son demasiado lentos. Creo que sé a qué te refieres, pero creo que esto es demasiado fuerte dependiendo de tu audiencia. AKS, por supuesto, es increíblemente lento, pero APR-CL y ECPP son lo suficientemente rápidos como para que algunas personas los usen. Son útiles para la criptografía paranoica, y útiles para personas que hacen cosas como primegapso factordbdonde uno tiene tiempo suficiente para querer primos probados.

[Mi comentario al respecto: cuando buscamos un número primo en un rango específico, utilizamos un enfoque de tamizado seguido de algunas pruebas probabilísticas relativamente rápidas. Solo entonces, si es que lo hacemos, ejecutamos una prueba determinista.]

En todas estas pruebas, la memoria no es un problema. Es un problema para AKS. Ver, por ejemplo, este eprint . Algo de esto depende de la implementación. Si uno implementa lo que el video de numberphile llama AKS (que en realidad es una generalización del pequeño teorema de Fermat), el uso de la memoria será extremadamente alto. El uso de una implementación NTL del algoritmo v1 o v6 como el documento al que se hace referencia dará como resultado una gran cantidad de memoria estúpida. Una buena implementación de v6 GMP todavía usará ~ 2 GB para un prime de 1024 bits, que es muchode memoria para un número tan pequeño. El uso de algunas de las mejoras de Bernstein y la segmentación binaria GMP conduce a un crecimiento mucho mejor (por ejemplo, ~ 120 MB para 1024 bits). Esto sigue siendo mucho más grande de lo que necesitan otros métodos, y no es de extrañar, será millones de veces más lento que APR-CL o ECPP.

Esta es una pregunta complicada debido a lo que se conoce como "constantes grandes / galácticas" asociadas con las inflexiones entre eficiencias de diferentes algoritmos. en otras palabras, el asociado con cada algoritmo diferente puede ocultar constantes muy grandes de modo que un más eficiente sobre otro basado únicamente en la complejidad asintótica / función " patadas "para muy grande . mi entendimiento es que AKS es "más eficiente" (que los algoritmos de la competencia) sólo para "mucho más grande " fuera de rango de utilidad práctica actual (y que precisaO ( f ( n ) ) O ( g ( n ) ) n n $O(f(n))$$O(f(n))$$O(g(n))$$n$$n$$n$ en realidad es muy difícil de calcular exactamente), pero las mejoras teóricas en la implementación del algoritmo (buscadas activamente por algunos) podrían cambiar eso en el futuro.

vi este artículo reciente sobre arxiv que analiza este tema en profundidad / detalle, no estoy seguro de lo que la gente piensa de él, no ha escuchado reacciones hasta ahora, parece que tal vez sea una tesis creada por el estudiante, pero posiblemente uno de los análisis más detallados / completos de Uso práctico del algoritmo disponible.

• Prueba de primalidad determinista: comprensión del algoritmo AKS Vijay Menon

• Potentes algoritmos demasiado complejos para implementar tcs.se