Pruebas de primalidad para números de 64 bits

Question

Para números muy pequeños, digamos 32 bits sin signo, probar todos los divisores hasta la raíz cuadrada es un enfoque muy decente. Se pueden hacer algunas optimizaciones para evitar probar todos los divisores, pero estas mejoras son marginales. La complejidad sigue siendo $O(\sqrt n)$ .

Por otro lado, existen pruebas de primalidad mucho más rápidas, pero son bastante sofisticadas y despliegan su eficacia para números mucho más largos.

¿Existe una solución intermedia, es decir, un algoritmo relativamente sencillo, que sea de utilidad práctica para, digamos, 64 bits sin signo, con un tiempo de ejecución objetivo inferior a 1 ms?

No busco la microoptimización del método de división exhaustiva. Busco un principio de funcionamiento mejor, de una complejidad razonable (y de tipo determinista).

---

Actualización:

Utilizando una versión Python de la prueba Miller-Rabin del código Rosetta, el tiempo para el prime $2^{64}-59=18446744073709551557$ es $0.7$ ms. (Aunque esto no es una prueba suficiente porque nada dice que estemos en el peor de los casos).

http://rosettacode.org/wiki/Miller%E2%80%93Rabin_primality_test#Python:_Proved_correct_up_to_large_N

Y supongo que este código se puede mejorar para aumentar la velocidad.

Answer 1

Creo que alguna versión del (determinista) Prueba de Miller-Rabin debería funcionar. Suele utilizarse como prueba probabilística para números muy grandes, pero puede reutilizarse como prueba determinista para rangos fijos más pequeños.

El núcleo de la prueba Miller-Rabin es la noción de un "primo probable" para alguna base $a$ . En concreto $n$ sea un primo impar, y escribamos $n - 1 = d \times 2^s$ para algunos impar $d$ . Entonces, se deduce que $a^d \equiv 1 \pmod{n}$ o $a^{d 2^r} \equiv -1 \pmod{n}$ para algunos $0 \leq r < s$ . (La página de la wikipedia tiene un razonamiento al respecto).

Si $n$ es un número cualquiera, y $a<n$ podríamos ejecutar la misma prueba, y si esa prueba pasara llamaríamos a $n$ a pseudoprimo fuerte para la base $a$ . La prueba habitual de Miller-Rabin se basa en hacer esto para un montón de diferentes (elegidos al azar) $a$ y algún argumento teórico numérico que diga que si $n$ es compuesto, la probabilidad de no encontrar un $a$ demostrando que esto es muy poco (después de probar muchos de ellos).

Sin embargo, si hay que creer a Wikipedia (no he seguido la referencia), entonces por $n < 2^{64}$ basta con comprobar $a \in \{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37\}$ . De alguna manera no hay números compuestos por debajo de $2^{64}$ que son un pseudoprimo fuerte para tous estos $a$ .

La prueba anterior es muy rápida, y en total la prueba principal requeriría como mucho $12 \times 64$ exponencias modulares (será muy inferior a 1 ms). Para $n$ podría incluso utilizar una lista más pequeña de posibles $a$ 's.

Answer 2

oeis/A014233 dice:

La primalidad de los números $\lt 2^{64}$ puede determinarse como pseudoprimalidad a todas las bases primos $\le 37$ .

La referencia es el reciente documento Pseudoprimas fuertes a doce bases primos por Sorenson y Webster.

Para el código, véase Prime64 y también el primos en FreeBSD, especialmente spsp.c .