Bases requeridas para la prueba principal con Miller-Rabin hasta$2^{63}-1$

Question

Esta página web (así como Wikipedia) explica cómo se puede utilizar el de Miller-Rabin prueba para determinar si un número en un rango determinado es primo. El tamaño de la gama determina el número de bases de la prueba. Por ejemplo:

Si $n < 9,080,191$ es una base $31$ y base $73$ fuerte probable primo, entonces $n$ es primo.

Si $n < 2,152,302,898,747$ es una base $2, 3, 5, 7,$ $11$ fuerte probable primo, entonces $n$ es primo.

¿Cuántas bases debo prueba de manera determinista saber si el entero $n < 2^{63}-1$ es primo?

Como uno puede adivinar por el obligado, estoy interesado en el uso de este enfoque para la primalidad de pruebas en los programas. Suponiendo la verdad de la extensión de la hipótesis de Riemann (que yo estaría dispuesto a hacer, dado que estoy usando este código simplemente para las competiciones y/o "juguete" de los problemas, pero no para las aplicaciones de alto riesgo), es suficiente para probar todas las bases de $a$ en el rango $1<a<2\log^2(n)$.

Reducir el número de bases que necesito comprobar podría mejorar dramáticamente el tiempo de ejecución de mi código; por lo tanto, me preguntaba si había un menor número de bases.

Answer 1

De acuerdo con A014233 ,

$a(12) > 2^{64}$. Por lo tanto, la primalidad de los números$< 2^{64}$ se puede determinar mediante la afirmación de una fuerte pseudoprimidad para todas las bases principales$\leqslant 37 (= \text{prime}(12))$. Las pruebas para bases primarias$\leqslant 31$ no son suficientes, ya que$a(11) < 2^{64}$ y$a(11)$ es una pseudoprime fuerte para todas las bases principales$\leqslant 31 (= \text{prime}(11))$. [Joerg Arndt, 4 de julio de 2012]

ps

Answer 2

Si, por alguna razón, usted insiste en que sólo el uso de la primera n primer bases, entonces usted necesita 12 bases para cubrir los 64 bits de espacio. Si utiliza algunos de los mejores conjuntos de personas que han encontrado, a continuación, lo mejor que sabemos es de 7 (http://miller-rabin.appspot.com/) y dependiendo del tamaño de entrada usted puede ser capaz de utilizar menos. Si usted está dispuesto a utilizar un 32k de la tabla hash, esto puede ser bajado a 3. El BPSW prueba puede ser hecho para ejecutarse sobre el costo de 2,7 x M-R pruebas y no requiere de la tabla hash.

Mi preferencia es para hacer un poco de juicio, de la división de números primos a 53, pero algunas personas les gusta menos), entonces 1 M-R si $n < 341531$, 2 M-R si $n < 1050535501$, de lo contrario BPSW. La AES Lucas variante utilizando Montgomery matemáticas es el más rápido para mí, pero depende de usted -- estándar, fuerte, extra fuerte, AES, y otros, han mostrado el trabajo. Sólo asegúrese de probar lo que usas.