La forma más rápida de averiguar si un número dado es primo

Question

Dado un número aleatorio, ¿cuál sería la forma más rápida de averiguar si es primo?

Obviamente, uno podría simplemente iterar a través del número para ver si es divisible por algo, pero ¿puede implementar formas más rápidas de encontrar un número dado?

Answer 1

La respuesta depende del tamaño.

Para números inferiores a $2^{64}$ lo que he encontrado mejor es:

• Pruebas de mods simples para primos pequeños (2, 3, 5, ...). Yo compruebo los primos hasta el 53, pero es mejor que hagas una prueba para saber qué es lo que mejor funciona para ti. Las operaciones mod simples funcionan bien aquí. Recuerda tener en cuenta las entradas pequeñas.
• Para las entradas que encajan en 32 bits: (1) utilizar tipos de 32 bits, incluyendo para la prueba previa anterior, (2) mirar la división de prueba con una rueda mod-30 para entradas muy pequeñas, y (3) considerar el uso de una prueba M-R de base única con hash (ver Forišek y Jancina 2015 o mi código vinculado a continuación). Solo necesitas una tabla de 256 cortos para cubrir todo el rango con una prueba. Si no quieres hacer la prueba simple hashed, puedes usar dos pruebas M-R (bases 31,73) si es menor que 9080191, tres (bases 2,7,61) si es mayor. Estas son pruebas deterministas sin contraejemplos.
• Para 64 bits depende de sus implementaciones, pero he encontrado que usar el método anterior para entradas "pequeñas" (32 bits), y una prueba AES BPSW para valores más grandes funciona mejor. También mira el mejores bases de SPRP para obtener ideas para una solución escalonada que incluya resultados deterministas en no más de 7 pruebas. También hay soluciones de hashtags utilizando no más de 3 pruebas. Una vez más, todo esto es determinista si se implementa correctamente.

Sugiero hacer una verificación utilizando tanto pequeñas entradas como la base de datos de pseudoprima Feitsma SPRP-2 para asegurarse de que su código funciona. Ha habido algunos incidentes desafortunados en los que las pruebas de primalidad de las bibliotecas más utilizadas tenían errores.

Lo ideal es que quieras un código optimizado para las pruebas. Por ejemplo Código M-R x86-64 de Izykowski o mis ejemplos (este último utiliza las rutinas Montgomery de Izykowski para x86-64 si es posible). Mi código también muestra el uso de la prueba previa, la división de prueba con la rueda mod-30, la M-R de base simple con hash para las entradas de 32 bits, y la BPSW de AES para las de 64 bits.

Para números mayores que $2^{64}$ es de suponer que está utilizando algo como GMP. El conjunto exacto de operaciones que dan el mejor resultado dependerá en gran medida de tu biblioteca bigint y de tu plataforma. Lo que yo hago usando GMP, que es todo heurístico para empezar:

• Si se trata de una entrada minúscula, se envía a la división de juicios simples. Lo ideal sería enviar cualquier número de 64 bits a la solución completa anterior.
• Pequeños primos: mpz_even_p seguido de mpz_gcd_ui con uno o dos primores de tamaño ui.
• Primas más grandes: mpz_gcd con un primor calculado. La operación gcd de GMP está muy bien optimizada para entradas grandes, y funciona significativamente más rápido que hacer mpz_divisible_p en cada número. Haga una evaluación comparativa y ajústela como desee. Mi solución es un compromiso ya que no quiero que el cálculo o el uso de la memoria dado que la gente puede no llamarlo con entradas grandes, por lo que hago un gcd con los primos menos de 1009 en primer lugar, a continuación, si más de 700 bits voy a hacer primos menos de 40000, y si más de 300 bits primos menos de 10000. De nuevo, estos son sólo ejemplos que funcionaron para mi aplicación, pero cualquiera que sea el número real que utilices, esto es una prueba previa rápida.
• Véase la sección 4.45 de Menezes o el documento ISPEC 2005 de Park para la discusión del tiempo empleado en la división de pruebas frente a la prueba de primalidad. Para entradas más grandes (por ejemplo, 1600 o más bits) hago más pruebas de divisibilidad. Para menos de 3000 bits sólo un bucle de mpz_divisible_ui_p por encima de eso hago un simple colado de árboles. Obviamente se puede omitir esto (Pari lo hace, por ejemplo), pero hace las cosas mucho más rápidas para entradas de 10k+ dígitos.
• BPSW . Se trata de una prueba M-R de base 2 seguida de una prueba Lucas. IMO usted debe hacer una prueba fuerte (no sólo es mejor que la prueba estándar sino que es más rápida) o extra fuerte que puede ser aún más rápido. Pari hace una prueba casi extra fuerte que también funciona bien.
• En este punto puedes parar y llamarlo probablemente primo (lo que hace la mayoría de la gente), o añadir una o más pruebas M-R de base aleatoria y seguir llamándolo probablemente primo (Mathematica añade una con base 3, yo añado de 1 a 5 dependiendo del tamaño, FIPS 186-4 añade muchas), o podrías hacer una prueba.

En cuanto a las pruebas, hay que tener en cuenta algunos puntos:

• Para los números inferiores a $2^{64}$ debería haber utilizado BPSW o M-R determinista. Hecho.
• Cualquiera que sugiera utilizar el AKS en la práctica nunca lo ha ejecutado en números mayores de 10.000 y debería ser ignorado.
• Siempre hay que utilizar primero una prueba como la BPSW, ya que no tiene sentido perder el tiempo en pruebas costosas para los compuestos. La mayoría de los códigos de pruebas de primalidad ya lo hacen.
• Existen métodos mucho más rápidos para números de formas particulares, por ejemplo, la prueba de Lucas-Lehmer para los números de Mersenne.
• Las pruebas pueden ser sorprendentemente rápidas para números "pequeños". Una prueba de un primo de 40 dígitos puede hacerse en uno o dos milisegundos. 100 dígitos sólo requieren 30-50 milisegundos. Podemos hacer 200 dígitos en menos de un segundo.
• La tasa de crecimiento de los métodos modernos es del orden de la cuarta potencia del tamaño, por lo que, si bien comienza de forma agradable y rápida, no lo es en absoluto para los números grandes. Tomará una hora más o menos para números en el rango de 1200 dígitos (Primo con múltiples núcleos puede ser más rápido, pero el punto se mantiene). 20k dígitos le tomará a una máquina de múltiples núcleos trabajando de 1 a 4 meses para completar una prueba.
• BLS75 métodos y ECPP dar un certificado. Estos pueden verificarse en otro ordenador utilizando un software completamente diferente, y completarse mucho más rápido que la prueba real. Esto supone una gran ventaja frente a métodos como APR-CL y AKS que dicen "confía en mí, es de primera. A menos que mi programa tenga un error o mi hardware esté sobreacelerado y haga algo mal". Para números muy grandes, realmente quieres un certificado de algún tipo.

Algunos programas de pruebas disponibles:

• Primo . El software de prueba de primalidad público más rápido para grandes entradas. Muy recomendable. No es de código abierto, pero está disponible gratuitamente y se utiliza desde hace muchos años. Utiliza una interfaz de usuario, por lo que no es adecuado para los procesos automatizados. Mucho más rápido que cualquier otra cosa que conozco más allá de 1500 dígitos o así.
• APR-CL de WraithX . Fácil de usar en un programa GMP, y bastante rápido.
• Pari/GP . APR-CL, no es tan rápido como el de WraithX, pero si tienes GP instalado es súper fácil de usar.
• ECPP-DJ . Mi software de pruebas ECPP independiente. Incluye BPSW, AKS, ECPP, BLS75 teorema 5. Produce certificados. Incluye un verificador de certificados para Primo y su propio formato. Un solo hilo. Con el gran conjunto de polímeros es más rápido que cualquier otra cosa que haya probado hasta unos 500 dígitos. Sin embargo, no está bien ajustado para entradas de más de 2.000 dígitos.
• OpenPFGW . Tiene algunas buenas pruebas de estilo BLS75 (pruebas que implican encontrar factores parciales de N-1 y/o N+1). No tiene certificados. Su característica más destacada viene cuando se trata de números de varios miles de dígitos, donde el uso del código bignum rápido de Woltman le permite hacer muy pruebas rápidas de Fermat. Esto es una buena prueba previa cuando se trata de números grandes.

Hay grupos de investigación con código privado que también hacen pruebas de primalidad, pero eso no nos ayuda al resto. Por otro lado, estos grupos a veces publican artículos que describen sus métodos, lo que tiene un valor inmenso. Los documentos de Atkin y Morain son un gran material y permitieron que otros escribieran software independiente.

Answer 2

Para números pequeños es mejor la división de pruebas. Calcula la raíz cuadrada del número y comprueba que ningún primo menor que él divide el número. Puede resultar útil utilizar un producto de primos que (apenas) quepan dentro de una palabra de la máquina, para reducir el número de divisiones necesarias; en ese caso hay que tomar la DGC en lugar de limitarse a dividir.

Para números algo mayores, por ejemplo $10^6$ a $2^{64}$ Sugiero la prueba BPSW que se ha demostrado que no tiene contraejemplos a continuación $2^{64}$ .

Para números mayores, fastECPP es probablemente el mejor algoritmo disponible.