¿Cuáles son los pros y los contras de las diversas pruebas de primalidad desde un punto de vista computacional? Educación te da un futuro mejor

No estaba seguro de cómo estructurar una respuesta, así que seguiré con mi método habitual de muchas listas. Sería bueno tener esto en una narrativa coherente, y he estado pensando en escribir una conferencia sobre eso.

La breve sugerencia es que creo que desea investigar BPSW, las compensaciones de las diferentes opciones de base en Miller-Rabin, y tener una idea de los tiempos de prueba típicos. También debe comprender su caso de uso, por ejemplo, 64 bits o 20–500 dígitos o 500–10k dígitos o 10k + dígitos; adversario o no; cuánta optimización se desea; cuán importante es obtener resultados deterministas; etc.

Lista codificada. No es una mala idea probar entradas <5, por ejemplo. LibTomMath realiza una búsqueda lineal frente a los primeros 256, lo que no es óptimo. Esto rápidamente se vuelve difícil de manejar y creo que es una mala elección ir muy lejos.
División de prueba. Elimina la mayoría de los compuestos más rápido que cualquier otra cosa, lo que lo convierte en un primer paso esencial para las pruebas prácticas (por ejemplo, ¡el 50% de las entradas arbitrarias serán rechazadas después de solo mirar el último bit de la entrada!). Aquí hay muchas implementaciones y conjuntos de compensaciones diferentes. Por ejemplo, ¿pruebas probabilidades, usas una rueda mod-6, mod-30, etc., o pruebas solo primos? Esto último significa menos pruebas, pero luego necesita obtener los números primos, que más allá de los tamaños pequeños deben medirse contra los ahorros. Hay optimizaciones adicionales para convertir múltiples mods no nativos en un mod de gran número más 2+ mods nativos. Usar esto como la única prueba depende de las implementaciones de otras partes. Lo encontré más rápido bajo ~ 1M, pero eso depende en gran medida de las pruebas de la competencia (por ejemplo, con un MR hash de base única que usa matemáticas de Montgomery en x86_64 o PPC, el crossover es mucho más bajo).
Miller-Rabin para entradas de 64 bits. Si escribe un nuevo software, ya no debería usar pruebas probabilísticas para entradas de 64 bits. Debería estar utilizando uno de los conjuntos de bases deterministas. Esto reduce el número de pruebas a un máximo de 7 bases para un resultado completamente correcto. Con una pequeña tabla hash de 512 bytes, puede obtener resultados correctos para todas las entradas de 32 bits con una sola prueba. Este es el método actual más eficiente para entradas no triviales de 32 bits. Para 64 bits, puede usar las bases fijas 3–7 o usar tablas hash grandes (4k para 2 pruebas de hasta 2 ^ 49, o 32k para 3 pruebas de hasta 2 ^ 64).
BPSW para entradas de 64 bits. La prueba BPSW es un MR único con base 2, seguido de una prueba fuerte de Lucas (o variantes de la prueba de Lucas). Fue publicado en 1980 y no tiene contraejemplos conocidos de ningún tamaño. Es utilizado por la mayoría de los paquetes matemáticos, la mayoría de los cuales abandonaron las pruebas aleatorias de Miller-Rabin cuando se quemaron al dar resultados falsos (por ejemplo, los documentos de Pinch en la década de 1990). Se sabe que es determinista y correcto para todas las entradas de 64 bits. Dependiendo de la implementación, esto será computacionalmente alrededor de 2.5 a 4 veces el costo de una sola prueba de MR, típicamente alrededor de 3 veces. Esto lo hace más rápido que el uso de bases fijas óptimas para Miller-Rabin, y competitivo con las soluciones hash más conocidas.
Para entradas grandes (mayores que el tamaño nativo) que no son “muy grandes”, por lo tanto, entre 20 y 4000 dígitos, creo que la prueba BPSW es la mejor opción. No tiene contraejemplo conocido y será 2–5 veces más rápido que las pruebas probabilísticas estándar de Miller-Rabin con un número razonable de pruebas. Puede agregar una prueba adicional de Miller-Rabin de base aleatoria si lo desea. El uso de múltiples pruebas de Miller-Rabin no es malo para la mayoría de las aplicaciones con advertencias (por nombrar algunas: es menos eficiente, usar bases fijas más allá de los rangos deterministas es una idea terrible, usar secuencias pseudoaleatorias como GMP tiene desventajas claras pero usar bases realmente aleatorias hace que sea difícil probar / validar / reproducir problemas). Una nota adicional de que Sorensen / Weber 2015 da bases deterministas de MR buenas a ~ 2 ^ 81.
Actualmente, una vez más allá de 2k-4k dígitos, la biblioteca gwnum es computacionalmente más rápida que GMP u otras alternativas que conozco. La diferencia aumenta a medida que aumenta el tamaño de entrada, y con 100k dígitos se acerca a 10x. La programación que usa no es tan conveniente como GMP, ni está instalada en la mayoría de las computadoras. Sin embargo, cuando se trata de entradas grandes, una vez que se ha realizado el tamizado / división de prueba, es mejor usar esto (generalmente en una herramienta como OpenPFGW) para eliminar los compuestos. Por lo general, esto solo usa una prueba simple de Fermat, que en estos tamaños de entrada es realmente bastante precisa, aunque aún querríamos realizar otras pruebas.

Esto cubre la mayor parte de lo que se usa en las pruebas actuales de primalidad / composición para entradas de forma general (estoy ignorando por completo las formas de Mersenne, Proth, etc. que tienen métodos de prueba / prueba más eficientes).

—————————————————————————————————————————

A veces queremos una prueba. La codificación de estos es * mucho * más difícil que las pruebas de Miller-Rabin y Lucas, por lo que generalmente no se hacen por esa razón también. Una prueba de primalidad probable correctamente escrita y buena es mejor que una implementación de prueba con errores. La mayoría de las personas no se dan cuenta de lo rápido que corren en tamaños pequeños y de lo lento que son en tamaños grandes. Mucha gente escucha un poco sobre la prueba AKS y saca conclusiones completamente erróneas sobre cómo funciona en la práctica. Tenemos pruebas fáciles, rápidas y correctas para entradas <~ 2 ^ 81. Algunos paquetes matemáticos utilizan el conocimiento de que BPSW ha demostrado ser correcto para todas las entradas de 64 bits.

Los resultados de las pruebas probabilísticas son uno de:

Definitivamente compuesto
Probablemente primo (“probablemente” puede variar de “¿quizás?” A “publicar esto ahora si es falso”)

Los resultados para métodos o pruebas deterministas serían uno de:

Definitivamente compuesto
Definitivamente primo (posiblemente con datos que muestran por qué)
No estoy seguro (la implementación no produjo un resultado, que puede o no ser posible, o puede ser una afirmación, pero es importante que tengamos en cuenta esto y no devolvamos uno de los otros resultados).

El software de prueba típico primero ejecutará algo así como una prueba BPSW. Como escribí anteriormente, es un método eficiente para eliminar casi todos los compuestos (“casi” es tan pequeño que aún no hemos encontrado uno, aunque es casi seguro que existan).

División de prueba. Pequeños insumos (por ejemplo, menos de 1 millón).
BPSW (64 bits) o determinista Miller-Rabin (64 bits o ~ 81 bits). Como se ve, es bastante rápido.
BLS75 (del artículo de 1975) funciona sorprendentemente bien para entradas de ~ 60 dígitos si tiene un buen software de factorización. No escala en absoluto, y debe tener cuidado al verificar todas las condiciones. Puede dar certificados de primalidad que se pueden verificar fácilmente.
APR-CL. Rápido, utilizado por Pari / GP, David Cleaver tiene una buena implementación de código abierto, hay una nueva que se está revisando para FLINT. Puede ver en el gráfico cómo funciona bastante bien: las pruebas para entradas arbitrarias de 200 dígitos se terminan en menos de un segundo. El mayor inconveniente en mi opinión es la falta de un certificado, lo que significa que debe confiar en la implementación, ya que todo lo que tiene es el único resultado.
ECPP. El método actual más rápido en la práctica para entradas grandes. Primo es el software que se usa típicamente. Es gratis pero no de código abierto. Hay al menos otra implementación de código abierto. Devuelve certificados bien formados y hay dos programas independientes que validan las matemáticas. En mi opinión, esto lo hace enormemente más atractivo, ya que no tenemos que confiar en una sola implementación. Primo también posee la mayoría de los récords mundiales para las pruebas de forma general más grandes, actualmente de unos 30k dígitos. Con las computadoras domésticas rápidas actuales, probar entradas de 10k dígitos es una tarea normal.

AKS es muy lento en la práctica, y con las implementaciones actuales no será más rápido que APR-CL o ECPP para cualquier entrada de tamaño que podamos ejecutar utilizando todas las computadoras del planeta. Lo bueno de AKS son las bonitas líneas rectas en el gráfico, que es una representación de por qué apareció en los titulares. Pero en la práctica, la posición y la pendiente de esas líneas es demasiado alta con los algoritmos e implementaciones actuales.

—————————————————————————————————————————

Existen otras pruebas de composición que no se usan con tanta frecuencia. Por ejemplo:

Fermat Se usa para entradas muy grandes en PFGW, pero generalmente una prueba de Miller-Rabin es la misma velocidad, evita el problema de los números de Carmichael y es una prueba más fuerte.
Solvay-Strassen, también llamada prueba Euler-Jacobi o Euler. Mejor que Fermat, pero no ofrece ventajas reales sobre Miller-Rabin, y este último es una prueba más sólida.
Euler-Plumb. Colin Plumb hizo un trabajo sofisticado con la prueba de Euler, y es muy ligeramente más rápido que los demás (incluido Miller-Rabin), aunque fue una prueba decente. Es un subconjunto de la prueba Miller-Rabin base-2, por lo que es de uso limitado, pero hay algunos casos interesantes en los que podría usarse.
Variantes de Lucas, casi siempre utilizadas como parte de BPSW o una prueba de Frobenius. Baillie y Wagstaff dicen usar la prueba fuerte de Lucas para BPSW, mientras que Pomerance, Selfridge y Wagstaff solo indican una prueba de Lucas. Los pseudoprimos fuertes de Lucas son un subconjunto, por lo que generalmente se debe usar la prueba fuerte. También existe la prueba extrafuerte que agrega más condiciones (pero utiliza una selección de parámetros diferente para que los pseudoprimos no sean subconjuntos) y la variante “casi extrafuerte” de Pari / GP. Por último, existe la definición de Lucas de Bruckman que no se usa para las pruebas de primalidad, y Mathematica solía tener una variante no estándar y defectuosa para las pruebas de primalidad, que puede o no haberse actualizado.
Pruebas de Frobenius. En algunas formas (cuadrática), estos se pueden definir como una prueba BPSW más una prueba adicional (consulte el algoritmo de Crandall y Pomerance 3.6.9). No hay una selección de parámetros bien definida para la prueba cuadrática estándar. Hay una serie de pruebas derivadas de esto, incluida la prueba Frobenius-Underwood computacionalmente práctica y la prueba Frobenius-Khashin, así como otras complicadas como QFT, EQFT, SQFT, MQFT. No conozco ninguna implementación del último grupo, pero se han utilizado las primeras (mi software tiene implementaciones de ellas).
Pruebas de Fibonacci y Pell. No veo ningún punto de esto en las pruebas de Lucas.
Perrin Interesante porque los pseudoprimos son raros. Es muy ineficaz desde el punto de vista informático y requiere una serie de trucos en las implementaciones. En el mejor de los casos, es 3 veces más lento que una prueba de Lucas, y las implementaciones típicas serán 100 veces más lentas. No hay ninguna ventaja real para este trabajo adicional.
Catalán. Intrigante porque los pseudoprimos son extremadamente raros (solo se conocen 3). Computacionalmente una pesadilla.