c++ - teorema - teoria de los numeros primos
El algoritmo más rápido para la prueba de primalidad (10)
Cobbal y Grokus tienen razón. La prueba de Miller-Rabin es la más útil de los algoritmos disponibles. Sí, es probabilístico, pero realmente no debería asustarte. La prueba es la más ampliamente utilizada para fines prácticos.
Tenga en cuenta que la probabilidad de falsos positivos (no hay falsos negativos) puede hacerse arbitrariamente pequeña repitiendo la prueba.
Necesito probar primalidad en intervalos entre números que son realmente grandes (en el rango de larga duración), entonces necesito algún algoritmo rápido para verificar si un número es primo o no. Por favor sugiere tus ideas.
Creo que la prueba de primalidad de corriente asintóticamente más rápida (no probabilística) es la "AKS mejorada de Lenstra / Pomerance", que tiene una complejidad que es esencialmente O (n ^ 6).
Sin embargo, el rango de long long (asumiendo un sistema típico donde ese es un entero de 64 bits) no es tan grande. En particular, solo hay ~ 200 millones de primos de menos de 2 ^ 32, por lo que se usa una prueba probabilística rápida, seguida de una división de prueba con una lista precalculada de primos (o simplemente buscando el número en una lista de primos, si tiene uno) ) sería bastante rápido en ese rango, y es probablemente la forma correcta de hacerlo.
El más rápido probablemente sería buscarlo en una lista precalculada de primos. Vea aquí, por ejemplo , tienen hasta 2 ^ 43112609-1 (primo conocido más grande).
El mejor algoritmo lo mejor de mi vista es "prueba de primalidad ALI".
Mire mi respuesta aquí:
cómo probar un número primo de 1000 dígitos de largo?
La prueba es muy rápida. Si está trabajando en el rango de 64 bits o menor, puede agregar un GCD con 30030 para ahorrar un poco de tiempo para la mayoría de los números.
Se me ocurrió un algoritmo realmente bueno, que es mucho más rápido que verificar todos los divisores, lo que por supuesto también me permite descifrar el cifrado de clave pública.
Espera, solo necesito cerrar la ventana, hay todos estos helicópteros negros arriba ........
(O mira ¿Cómo puedo probar la primalidad? )
Si quieres probar la idea de primalidad, entonces la prueba de primalidad Baillie PSW es una buena opción. Esta prueba hace una fuerte prueba de pseudoprima y una prueba de Lucas y, por lo tanto, es muy rápida. Se espera que existan algunos compuestos que pasen esta prueba, pero hasta ahora no se conocen, y ciertamente no hay ninguna excepción debajo de 10 15 . Una variante de esta prueba se usa, por ejemplo, en Mathematica.
Sugeriría la biblioteca GNU MP que usa el algoritmo Miller-Rabin . Lo he usado por unos meses y es muy rápido.
Específicamente, la función mpz_probab_prime_p hace esto, también puede usar otra función mpz_nextprime para encontrar el siguiente número primo mayor que un número. Puedo publicar muestras de código si lo desea.
Un buen método es la prueba Miller-Rabin . Sin embargo, debe tenerse en cuenta que esta es solo una prueba probabilística.