Prueba de primalidad de Miller-Rabin

La prueba de primalidad de Miller-Rabin o prueba de primalidad de Rabin-Miller es una prueba de primalidad probabilística : un algoritmo que determina si es probable que un número dado sea primo , similar a la prueba de primalidad de Fermat y a la prueba de primalidad de Solovay-Strassen .

Tiene importancia histórica en la búsqueda de una prueba de primalidad determinista en tiempo polinómico . Su variante probabilística sigue utilizándose ampliamente en la práctica, como una de las pruebas más simples y rápidas que se conocen.

Gary L. Miller descubrió la prueba en 1976. La versión de Miller de la prueba es determinista , pero su exactitud se basa en la hipótesis de Riemann extendida no probada . ^[1] Michael O. Rabin la modificó para obtener un algoritmo probabilístico incondicional en 1980. ^[2]^[a]

Conceptos matemáticos

De manera similar a las pruebas de Fermat y Solovay-Strassen, la prueba de primalidad de Miller-Rabin verifica si una propiedad específica, que se sabe que es válida para valores primos, es válida para el número bajo prueba.

Primos probables fuertes

La propiedad es la siguiente. Para un entero impar dado n > 2 , escribamos n − 1 como 2 ^s d donde s es un entero positivo y d es un entero positivo impar. Consideremos un entero a , llamado base , que es coprimo con n . Entonces, se dice que n es un primo probable fuerte con base a si se cumple una de estas relaciones de congruencia :

$a^{d}\equiv 1{\pmod {n}}$ ;
$a^{2^{r}d}\equiv -1{\pmod {n}}$ para algunos 0 ≤ r < s .

Esto se simplifica a comprobar primero y luego los valores sucesivos de r. Para cada valor de r, el valor de la expresión se puede calcular utilizando el valor obtenido para el valor anterior de r elevando al cuadrado bajo el módulo de n. $a^{d}{\bmod {n}}=1$ $a^{2^{r}d}=n-1$

La idea detrás de esta prueba es que cuando n es un primo impar, pasa la prueba debido a dos hechos:

por el pequeño teorema de Fermat , (esta propiedad por sí sola define la noción más débil de primo probable en base a , en la que se basa la prueba de Fermat); $a^{n-1}\equiv 1{\pmod {n}}$
Las únicas raíces cuadradas de 1 módulo n son 1 y −1.

Por lo tanto, por contraposición , si n no es un primo probable fuerte para la base a , entonces n es definitivamente compuesto, y a se llama testigo de la composición de n .

Sin embargo, esta propiedad no es una caracterización exacta de los números primos. Si n es compuesto, puede ser, no obstante, un primo probable fuerte de base a , en cuyo caso se denomina pseudoprimo fuerte y a es un mentiroso fuerte .

Elección de bases

Ningún número compuesto es un pseudoprimo fuerte para todas las bases al mismo tiempo (contrariamente a la prueba de primalidad de Fermat para la que existen pseudoprimos de Fermat para todas las bases: los números de Carmichael ). Sin embargo, no se conoce una forma sencilla de encontrar un testigo. Una solución ingenua es probar todas las bases posibles, lo que produce un algoritmo determinista ineficiente. La prueba de Miller es una variante más eficiente de esto (ver la sección Prueba de Miller a continuación).

Otra solución es elegir una base al azar. Esto produce una prueba probabilística rápida . Cuando n es compuesto, la mayoría de las bases son testigos, por lo que la prueba detectará n como compuesto con una probabilidad razonablemente alta (ver la sección Precisión a continuación). Podemos reducir rápidamente la probabilidad de un falso positivo a una tasa arbitrariamente pequeña, combinando el resultado de tantas bases elegidas independientemente como sea necesario para lograr dicha tasa. Esta es la prueba de Miller-Rabin. Parece haber rendimientos decrecientes al probar muchas bases, porque si n es un pseudoprimo para alguna base, entonces parece más probable que sea un pseudoprimo para otra base. ^[4]^{: §8}

Nótese que $a d \equiv 1 (mod n)$ se cumple trivialmente para $a \equiv 1 (mod n)$ , porque la relación de congruencia es compatible con la exponenciación . Y $a d = a 20 d \equiv -1 (mod n)$ se cumple trivialmente para $a \equiv -1 (mod n)$ ya que $d$ es impar, por la misma razón. Es por eso que $los a$ aleatorios generalmente se eligen en el intervalo $1 < a < n - 1$ .

Para probar un número arbitrario $de n$ , es esencial elegir bases al azar, ya que no conocemos la distribución de testigos y mentirosos fuertes entre los números 2, 3, ..., $n - 2.$ [ ^b]

Sin embargo, un conjunto preseleccionado de unas pocas bases pequeñas garantiza la identificación de todos los compuestos hasta un máximo precalculado. Este máximo suele ser bastante grande en comparación con las bases. Esto permite realizar pruebas deterministas muy rápidas para valores n suficientemente pequeños (consulte la sección Pruebas con conjuntos pequeños de bases a continuación).

Pruebas

Aquí hay una prueba de que, si n es primo, entonces las únicas raíces cuadradas de 1 módulo n son 1 y −1.

Prueba

Ciertamente, 1 y −1, cuando se elevan al cuadrado módulo n , siempre dan 1. Queda por demostrar que no hay otras raíces cuadradas de 1 módulo n . Este es un caso especial, aquí aplicado con el polinomio X ² − 1 sobre el cuerpo finito Z / n Z , del hecho más general de que un polinomio sobre algún cuerpo no tiene más raíces que su grado (este teorema se deduce de la existencia de una división euclidiana para polinomios ). A continuación sigue una prueba más elemental. Supóngase que x es una raíz cuadrada de 1 módulo n . Entonces:

(x-1)(x+1)=x^{2}-1\equiv 0{\pmod {n}}.

En otras palabras, n divide al producto ( x − 1)( x + 1) . Por el lema de Euclides , dado que n es primo, divide a uno de los factores x − 1 o x + 1, lo que implica que x es congruente con 1 o −1 módulo n .

Aquí hay una prueba de que, si n es un primo impar, entonces es un primo probable fuerte para base a .

Prueba

Si n es un primo impar y escribimos n − 1= 2 ^s d donde s es un entero positivo y d es un entero positivo impar, por el pequeño teorema de Fermat:

a^{2^{s}d}\equiv 1{\pmod {n}}.

Cada término de la sucesión es una raíz cuadrada del término anterior. Como el primer término es congruente con 1, el segundo término es una raíz cuadrada de 1 módulo n . Por el lema anterior , es congruente con 1 o con −1 módulo n . Si es congruente con −1, hemos terminado. De lo contrario, es congruente con 1 y podemos iterar el razonamiento . Al final, uno de los términos es congruente con −1, o todos son congruentes con 1, y en particular el último término, a ^d , lo es. $a^{2^{s}d},a^{2^{s-1}d},\puntos ,a^{2d},a^{d}$

Ejemplo

Supongamos que queremos determinar si es primo. Escribimos , de modo que tenemos . Seleccionamos aleatoriamente un número tal que . ${\estilo de visualización n=221}$ $n-1{\text{ como }}2^{2}\times 55$ $s=2{\text{ y }}d=55$ ${\estilo de visualización a}$ $2\leq a\leq n-2$

Decir : $a=174$

${\begin{aligned}a^{{s^{0}}d}{\text{ mod }}n\rightarrow &174^{{2^{0}}55}{\text{ mod }}221\equiv 174^{55}\equiv 47{\text{. Como }}47\neq 1{\text{ y }}47\neq n-1{\text{, continuamos.}}\\&174^{{2^{1}}55}{\text{ mod }}221\equiv 174^{110}\equiv 220=n-1\end{aligned}}$

Dado que , o bien 221 es primo, o bien 174 es un mentiroso fuerte para 221. Probamos otro , aleatorio , esta vez eligiendo : $220\equiv -1{\text{mod}}n$ ${\estilo de visualización a}$ $a=137$

${\begin{aligned}a^{{s^{0}}d}{\text{ mod }}n\rightarrow &137^{{2^{0}}55}{\text{ mod }}221\equiv 137^{55}\equiv 188{\text{. Since }}188\neq 1{\text{ and }}188\neq n-1{\text{, we continue.}}\\&137^{{2^{1}}55}{\text{ mod }}221\equiv 137^{110}\equiv 205\neq n-1\end{aligned}}$

Por lo tanto, 137 es un testigo de la composición de 221, y 174 era, de hecho, un mentiroso empedernido. Nótese que esto no nos dice nada acerca de los factores de 221 (que son 13 y 17). Sin embargo, el ejemplo con 341 en una sección posterior muestra cómo estos cálculos a veces pueden producir un factor de n .

Para obtener una guía práctica sobre cómo elegir el valor de a, consulte Pruebas contra conjuntos pequeños de bases .

Prueba de Miller-Rabin

El algoritmo se puede escribir en pseudocódigo de la siguiente manera. El parámetro k determina la precisión de la prueba. Cuanto mayor sea el número de rondas, más preciso será el resultado. ^[6]

Entrada n.° 1 : n > 2, un entero impar que se probará para determinar su primalidad. Entrada n.° 2 : k , la cantidad de rondas de prueba a realizar. Salida : “ compuesto ” si se descubre que n es compuesto, “ probablemente primo ” en caso contrario.

sea  s > 0 y d impar > 0 tal que n − 1 = 2 ^s d  # factorizando potencias de 2 de n − 1 repita  k  veces : a ← random(2, n − 2) # n siempre es un primo probable en base 1 y n − 1 x ← a ^d mod n  repita  s  veces : y ← x ² mod n  si  y = 1 y x ≠ 1 y x ≠ n − 1 entonces  # raíz cuadrada no trivial de 1 módulo n  devuelve “ compuesto ” x ← y  si  y ≠ 1 entonces  devuelve “ compuesto ” devuelve “ probablemente primo ”

Complejidad

Usando el cuadrado repetido , el tiempo de ejecución de este algoritmo es $O (k log 3 n)$ , donde n es el número probado para primalidad, y k es el número de rondas realizadas; por lo tanto, este es un algoritmo eficiente de tiempo polinomial. La multiplicación basada en FFT ( algoritmo de Harvey-Hoeven ) puede reducir el tiempo de ejecución a $O(k log 2 n log log n) = Õ (k log 2 n)$ .

Exactitud

El error cometido por la prueba de primalidad se mide por la probabilidad de que un número compuesto sea declarado probablemente primo. Cuanto más bases a se prueben, mejor será la precisión de la prueba. Se puede demostrar que si n es compuesto, entonces como máximo ⁠1/4⁠ de las bases a son mentirosos fuertes para n . ^[2]^[7] Como consecuencia, si n es compuesto, entonces ejecutar k iteraciones de la prueba de Miller-Rabin declarará que n es probablemente primo con una probabilidad de como máximo 4 ^{− k} .

Esto es una mejora con respecto a la prueba de Solovay–Strassen , cuyo límite de error en el peor de los casos es 2 ^{− k} . Además, la prueba de Miller–Rabin es estrictamente más fuerte que la prueba de Solovay–Strassen en el sentido de que para cada compuesto n , el conjunto de mentirosos fuertes para n es un subconjunto del conjunto de mentirosos de Euler para n , y para muchos n , el subconjunto es apropiado.

Además, para valores grandes de n , la probabilidad de que un número compuesto sea declarado probablemente primo es a menudo significativamente menor que 4 ^{− k} . Por ejemplo, para la mayoría de los números n , esta probabilidad está limitada por 8 ^{− k} ; la proporción de números n que invalidan este límite superior se desvanece cuando consideramos valores mayores de n . ^[8] Por lo tanto, el caso promedio tiene una precisión mucho mejor que 4 ^{− k} , un hecho que puede explotarse para generar primos probables (ver más abajo). Sin embargo, no se debe confiar en dichos límites de error mejorados para verificar primos cuya distribución de probabilidad no está controlada, ya que un adversario criptográfico podría enviar un pseudoprimo cuidadosamente elegido para vencer la prueba de primalidad. ^[c] En tales contextos, solo se puede confiar en el límite de error del peor caso de 4 ^{− k .}

La medida de error anterior es la probabilidad de que un número compuesto sea declarado como un primo probable fuerte después de k rondas de prueba; en palabras matemáticas, es la probabilidad condicional donde P es el evento de que el número que se está probando sea primo, y MR _k es el evento de que pase la prueba de Miller-Rabin con k rondas. En cambio, a menudo nos interesa la probabilidad condicional inversa : la probabilidad de que un número que ha sido declarado como un primo probable fuerte sea de hecho compuesto. Estas dos probabilidades están relacionadas por la ley de Bayes : $\Pr(M\!R_{k}\mid \lnot P)$ $\Pr(\lnot P\mid M\!R_{k})$

{\begin{aligned}\Pr(\lnot P\mid M\!R_{k})&={\frac {\Pr(\lnot P\land M\!R_{k})}{\Pr(\lnot P\land M\!R_{k})+\Pr(P\land M\!R_{k})}}\\&={\frac {1}{1+{\frac {\Pr(M\!R_{k}\mid P)}{\Pr(M\!R_{k}\mid \lnot P)}}{\frac {\Pr(P)}{\Pr(\lnot P)}}}}\\&={\frac {1}{1+{\frac {1}{\Pr(M\!R_{k}\mid \lnot P)}}{\frac {\Pr(P)}{1-\Pr(P)}}}}\end{aligned}}

En la última ecuación, simplificamos la expresión utilizando el hecho de que todos los números primos se informan correctamente como primos probables fuertes (la prueba no tiene ningún falso negativo ). Al eliminar la parte izquierda del denominador , derivamos un límite superior simple:

\Pr(\lnot P\mid M\!R_{k})<\Pr(M\!R_{k}\mid \lnot P)\left({\tfrac {1}{\Pr(P)}}-1\right)

Por lo tanto, esta probabilidad condicional está relacionada no solo con la medida de error discutida anteriormente (que está limitada por 4 ^{− k}  ), sino también con la distribución de probabilidad del número de entrada. En el caso general, como se dijo antes, esta distribución está controlada por un adversario criptográfico, por lo tanto desconocido, por lo que no podemos deducir mucho sobre . Sin embargo, en el caso en que usamos la prueba de Miller-Rabin para generar primos (ver más abajo), la distribución es elegida por el propio generador, por lo que podemos aprovechar este resultado. $\Pr(\lnot P\mid M\!R_{k})$

Variantes deterministas

Prueba de Miller

El algoritmo de Miller-Rabin puede volverse determinista probando todos los valores posibles de a por debajo de un cierto límite. Tomar n como límite implicaría $O(n)$ ensayos, por lo tanto, el tiempo de ejecución sería exponencial con respecto al tamaño $log n$ de la entrada. Para mejorar el tiempo de ejecución, el desafío es entonces reducir el límite tanto como sea posible mientras se mantiene la confiabilidad de la prueba.

Si el número probado n es compuesto, los mentirosos fuertes a coprimos con n están contenidos en un subgrupo propio del grupo ( Z / n Z )*, lo que significa que si probamos todos los a de un conjunto que genera ( Z / n Z )*, uno de ellos debe estar fuera de dicho subgrupo, por lo tanto debe ser un testigo de la composición de n . Suponiendo la verdad de la hipótesis de Riemann extendida (ERH), se sabe que el grupo es generado por sus elementos más pequeños que $O(( ln n) 2)$ , lo que ya fue notado por Miller. ^[1] La constante involucrada en la notación Big O fue reducida a 2 por Eric Bach . ^[10] Esto conduce al siguiente algoritmo de prueba de primalidad, conocido como la prueba de Miller , que es determinista asumiendo la GRH:

Entrada : n > 2, un entero impar que se debe probar para determinar su primalidad Salida : “ compuesto ” si n es compuesto, “ primo ” en caso contrario

sea  s > 0 y d impar > 0 tal que n − 1 = 2 ^s d  # factorizando potencias de 2 de n − 1 para todo  a  en el rango [2, min( n − 2, ⌊2(ln n ) ² ⌋)]: x ← a ^d mod n  repetir  s  veces : y ← x ² mod n  si  y = 1 y x ≠ 1 y x ≠ n − 1 entonces  # raíz cuadrada no trivial de 1 módulo n  devuelve “ compuesto ” x ← y  si  y ≠ 1 entonces  devuelve “ compuesto ” devuelve “ primo ”

No se necesita toda la potencia de la hipótesis de Riemann generalizada para garantizar la exactitud de la prueba: como tratamos con subgrupos de índice par , basta con suponer la validez de GRH para caracteres de Dirichlet cuadráticos . ^[7]

El tiempo de ejecución del algoritmo es, en la notación soft-O , $Õ((log n) 4)$ (usando multiplicación basada en FFT).

La prueba de Miller no se utiliza en la práctica. Para la mayoría de los propósitos, el uso adecuado de la prueba probabilística de Miller-Rabin o la prueba de primalidad de Baillie-PSW brinda suficiente confianza y, al mismo tiempo, se ejecuta mucho más rápido. También es más lenta en la práctica que los métodos de prueba comúnmente utilizados, como APR-CL y ECPP, que brindan resultados que no se basan en suposiciones no probadas. Para fines teóricos que requieren un algoritmo de tiempo polinomial determinista, fue reemplazada por la prueba de primalidad AKS , que tampoco se basa en suposiciones no probadas.

Pruebas contra pequeños conjuntos de bases

Cuando el número n a probar es pequeño, no es necesario probar todos $los a < 2(ln n) 2$ , ya que se sabe que conjuntos mucho más pequeños de testigos potenciales son suficientes. Por ejemplo, Pomerance, Selfridge, Wagstaff ^[4] y Jaeschke ^[11] han verificado que

si n < 2,047, es suficiente probar a = 2;
si n < 1.373.653, basta probar a = 2 y 3;
si n < 9.080.191, basta probar a = 31 y 73;
si n < 25.326.001, es suficiente probar a = 2, 3 y 5;
si n < 3.215.031.751, es suficiente probar a = 2, 3, 5 y 7;
si n < 4.759.123.141, es suficiente probar a = 2, 7 y 61;
si n < 1.122.004.669.633, es suficiente probar a = 2, 13, 23 y 1662803;
si n < 2.152.302.898.747, es suficiente probar a = 2, 3, 5, 7 y 11;
si n < 3.474.749.660.383, es suficiente probar a = 2, 3, 5, 7, 11 y 13;
Si n < 341.550.071.728.321, es suficiente probar a = 2, 3, 5, 7, 11, 13 y 17.

Utilizando el trabajo de Feitsma y Galway que enumeraron todos los pseudoprimos de base 2 en 2010, esto se amplió (ver OEIS : A014233 ), y el primer resultado se mostró más tarde utilizando métodos diferentes en Jiang y Deng: ^[12]

si n < 3.825.123.056.546.413.051, es suficiente probar a = 2, 3, 5, 7, 11, 13, 17, 19 y 23.
si n < 18.446.744.073.709.551.616 = 2 ⁶⁴ , es suficiente probar a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 y 37.

Sorenson y Webster ^[13] verifican lo anterior y calculan resultados precisos para estos resultados mayores de 64 bits:

si n < 318.665.857.834.031.151.167.461, es suficiente probar a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 y 37.
si n < 3.317.044.064.679.887.385.961.981, es suficiente probar a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 y 41.

Existen otros criterios de este tipo, a menudo más eficientes (se requieren menos bases) que los mostrados anteriormente. ^[14]^[15]^[16]^[17] Proporcionan pruebas de primalidad deterministas muy rápidas para números en el rango apropiado, sin ninguna suposición.

Hay una pequeña lista de testigos potenciales para cada tamaño de entrada posible (como máximo b valores para números de b bits). Sin embargo, ningún conjunto finito de bases es suficiente para todos los números compuestos. Alford, Granville y Pomerance han demostrado que existen infinitos números compuestos n cuyo testigo de composición más pequeño es al menos $(ln n) 1/(3ln ln ln n)$ . ^[18] También argumentan heurísticamente que el número más pequeño w tal que cada número compuesto por debajo de n tiene un testigo de composición menor que w debería ser de orden $Θ (log n log log n).$

Variantes para encontrar factores

Al insertar cálculos del máximo común divisor en el algoritmo anterior, a veces podemos obtener un factor de n en lugar de simplemente determinar que n es compuesto. Esto ocurre, por ejemplo, cuando n es un primo probable de base a pero no un primo probable fuerte de base a . ^[19]^{: 1402}

Si x es una raíz cuadrada no trivial de 1 módulo n ,

como $x 2 \equiv 1 (mod n)$ , sabemos que n divide $a x 2 - 1 = (x - 1)(x + 1)$ ;
como $x ≢ \pm1 (mod n)$ , sabemos que n no divide $a x - 1$ ni $a x + 1$ .

De esto deducimos que $A = mcd(x - 1, n)$ y $B = mcd(x + 1, n)$ son factores no triviales (no necesariamente primos) de n (de hecho, dado que n es impar, estos factores son coprimos y n = AB ). Por lo tanto, si la factorización es un objetivo, estos cálculos de mcd se pueden insertar en el algoritmo con un pequeño costo computacional adicional. Esto conduce al siguiente pseudocódigo, donde se resalta el código agregado o modificado:

Entrada n.° 1 : n > 2, un entero impar que se probará para determinar su primalidad. Entrada n.° 2 : k , la cantidad de rondas de prueba a realizar. Salida : (“ múltiplo de ”, m ) si se encuentra un factor no trivial m de n , “ compuesto ” si se encuentra que n es compuesto de otra manera. “ probablemente primordial ” de lo contrario

sea  s > 0 y d impar > 0 tal que n − 1 = 2 ^s d # factorizando potencias de 2 de n − 1 repita  k  veces : a ← random(2, n − 2) # n siempre es un primo probable en base 1 y n − 1  x ← a ^d mod n  repita  s  veces : y ← x ² mod n  si  y = 1 y x ≠ 1 y x ≠ n − 1 entonces  # raíz cuadrada no trivial de 1 módulo n  devuelve (“ múltiplo de ”, mcd( x − 1, n ))  x ← y  si  y ≠ 1 entonces  devuelve “ compuesto ” devuelve “ probablemente primo ”

Este no es un algoritmo de factorización probabilística porque solo es capaz de encontrar factores para números n que sean pseudoprimos en base a (en otras palabras, para números n tales que $a n -1 \equiv 1 mod n$ ). Para otros números, el algoritmo solo devuelve “ compuesto ” sin más información.

Por ejemplo, considere n = 341 y a = 2. Tenemos $n - 1 = 85 \times 4$ . Entonces $285 mod 341 = 32$ y $322 mod 341 = 1$ . Esto nos dice que n es un pseudoprimo base 2, pero no un pseudoprimo base 2 fuerte. Al calcular un mcd en esta etapa, encontramos un factor de 341: $mcd(32 - 1, 341) = 31$ . De hecho, $341 = 11 \times 31$ .

Para encontrar factores con mayor frecuencia, las mismas ideas también se pueden aplicar a las raíces cuadradas de −1 (o cualquier otro número). Esta estrategia se puede implementar explotando el conocimiento de rondas anteriores de la prueba Miller-Rabin. En esas rondas, es posible que hayamos identificado una raíz cuadrada módulo n de −1, digamos R . Entonces, cuando $x 2 mod n = n - 1$ , podemos comparar el valor de x con R : si x no es ni R ni n − R , entonces $mcd(x - R, n)$ y $mcd(x + R, n)$ son factores no triviales de n . ^[14]

Generación de primos probables

La prueba de Miller-Rabin se puede utilizar para generar primos probables fuertes, simplemente extrayendo números enteros al azar hasta que uno pase la prueba. Este algoritmo termina casi con seguridad (ya que en cada iteración existe la posibilidad de extraer un número primo). El pseudocódigo para generar primos probables fuertes de b bits (con el bit más significativo establecido) es el siguiente:

Entrada n.° 1 : b , la cantidad de bits del resultado Entrada n.° 2 : k , la cantidad de rondas de prueba a realizar Salida : un primo probable fuerte n

mientras sea verdadero: Elija un entero impar aleatorio n en el rango [2 ^{b −1} , 2 ^b −1] si la prueba de Miller-Rabin con entradas n y k devuelve “ probablemente primo ”, entonces  devuelva  n

Complejidad

Por supuesto, el tiempo de ejecución en el peor de los casos es infinito, ya que el bucle externo puede no terminar nunca, pero eso sucede con una probabilidad cero. Según la distribución geométrica , el número esperado de extracciones es (reutilizando las notaciones anteriores). ${\tfrac {1}{\Pr(M\!R_{k})}}$

Como cualquier número primo pasa la prueba, la probabilidad de ser primo da un límite inferior aproximado a la probabilidad de pasar la prueba. Si extraemos números enteros impares de manera uniforme en el rango [2 ^{b −1} , 2 ^b −1], obtenemos:

\Pr(M\!R_{k})>\Pr(P)={\frac {\pi \left(2^{b}\right)-\pi \left(2^{b-1}\right)}{2^{b-2}}}

donde π es la función de conteo de primos . Usando una expansión asintótica de π (una extensión del teorema de los números primos ), podemos aproximar esta probabilidad cuando b crece hacia el infinito. Encontramos:

\Pr(P)={\tfrac {2}{\ln 2}}b^{-1}+{\mathcal {O}}\left(b^{-3}\right)

{\tfrac {1}{\Pr(P)}}={\tfrac {\ln 2}{2}}b+{\mathcal {O}}\left(b^{-1}\right)

Por lo tanto, podemos esperar que el generador no ejecute más pruebas de Miller-Rabin que un número proporcional a b . Teniendo en cuenta la complejidad del peor caso de cada prueba de Miller-Rabin (ver anteriormente), el tiempo de ejecución esperado del generador con entradas b y k está entonces limitado por $O(k b 4)$ (o $Õ(k b 3)$ usando la multiplicación basada en FFT).

Exactitud

La medida de error de este generador es la probabilidad de que produzca un número compuesto.

Utilizando la relación entre las probabilidades condicionales (mostradas en una sección anterior) y el comportamiento asintótico de (mostrado justo antes), a esta medida de error se le puede dar un límite superior aproximado: $\Pr(P)$

\Pr(\lnot P\mid M\!R_{k})<\Pr(M\!R_{k}\mid \lnot P)\left({\tfrac {1}{\Pr(P)}}-1\right)\leq 4^{-k}\left({\tfrac {\ln 2}{2}}b-1+{\mathcal {O}}\left(b^{-1}\right)\right).

Por lo tanto, para un valor b suficientemente grande , esta medida de error es menor que . Sin embargo, existen límites mucho mejores. ${\tfrac {\ln 2}{2}}4^{-k}b$

Utilizando el hecho de que la prueba de Miller-Rabin en sí misma a menudo tiene un límite de error mucho menor que 4 ^{− k} (ver anteriormente), Damgård , Landrock y Pomerance derivaron varios límites de error para el generador, con varias clases de parámetros b y k . ^[8] Estos límites de error permiten a un implementador elegir un k razonable para una precisión deseada.

Uno de estos límites de error es 4 ^{− k} , que se cumple para todos los valores b ≥ 2 (los autores solo lo demostraron para b ≥ 51, mientras que Ronald Burthe Jr. completó la prueba con los valores restantes 2 ≤ b ≤ 50 ^[20] ). Nuevamente, este límite simple se puede mejorar para valores grandes de b . Por ejemplo, otro límite derivado por los mismos autores es:

\left({\frac {1}{7}}b^{\frac {15}{4}}2^{-{\frac {b}{2}}}\right)4^{-k}

lo cual es válido para todos los valores b ≥ 21 y k ≥ b /4. Este límite es menor que 4 ^{− k} tan pronto como b ≥ 32.

Notas

^ A menudo se dice incorrectamente que la prueba de Miller-Rabin fue descubierta por MM Artjuhov ya en 1967; una lectura del artículo de Artjuhov ^[3] (en particular su Teorema E ) muestra que en realidad descubrió la prueba de Solovay-Strassen.
^ Por ejemplo, en 1995, Arnault proporciona un número compuesto de 397 dígitos para el cual todas las bases menores que 307 son mentirosas fuertes; la función Maple informó que este número era primo , porque implementó la prueba de Miller-Rabin con las bases específicas 2, 3, 5, 7 y 11. ^[5] isprime()
^ Por ejemplo, en 2018, Albrecht et al. pudieron construir, para muchas bibliotecas criptográficas como OpenSSL y GNU GMP , números compuestos que estas bibliotecas declararon primos, demostrando así que no se implementaron con un contexto adversario en mente. ^[9]

Referencias

^ ab Miller, Gary L. (1976), "Hipótesis de Riemann y pruebas de primalidad", Journal of Computer and System Sciences , 13 (3): 300–317, doi :10.1145/800116.803773, S2CID 10690396
^ ab Rabin, Michael O. (1980), "Algoritmo probabilístico para probar la primalidad", Journal of Number Theory , 12 (1): 128–138, doi :10.1016/0022-314X(80)90084-0
^ Artjuhov, MM (1966–1967), "Ciertos criterios de primalidad de números relacionados con el pequeño teorema de Fermat", Acta Arithmetica , 12 : 355–364, MR 0213289
^ ab Carl Pomerance ; John L. Selfridge ; Samuel S. Wagstaff, Jr. (julio de 1980). "Los pseudoprimos hasta 25 ⋅ 109" (PDF) . Matemáticas de la computación . 35 (151): 1003–1026. doi : 10.1090/S0025-5718-1980-0572872-7 .
^ F. Arnault (agosto de 1995). "Construcción de números de Carmichael que son pseudoprimos fuertes para varias bases". Journal of Symbolic Computation . 20 (2): 151–161. doi : 10.1006/jsco.1995.1042 .
^ Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009) [1990]. "31". Introducción a los algoritmos (3ª ed.). MIT Press y McGraw-Hill. págs. 968–971. ISBN 0-262-03384-4.
^ ab Schoof, René (2004), "Cuatro algoritmos de prueba de primalidad" (PDF) , Teoría algorítmica de números: redes, campos numéricos, curvas y criptografía , Cambridge University Press, ISBN 978-0-521-80854-5
^ ab Damgård, I. ; Landrock, P. y Pomerance, C. (1993), "Estimaciones de error de caso promedio para la prueba de primos probables fuertes" (PDF) , Matemáticas de la computación , 61 (203): 177–194, Bibcode :1993MaCom..61..177D, doi :10.2307/2152945, JSTOR 2152945
^ Martin R. Albrecht; Jake Massimo; Kenneth G. Paterson; Juraj Somorovsky (15 de octubre de 2018). Primaria y prejuicio: pruebas de primalidad en condiciones adversas (PDF) . Conferencia ACM SIGSAC sobre seguridad informática y de comunicaciones 2018. Toronto: Association for Computing Machinery . págs. 281–298. doi :10.1145/3243734.3243787.
^ Bach, Eric (1990), "Límites explícitos para pruebas de primalidad y problemas relacionados", Mathematics of Computation , 55 (191): 355–380, Bibcode :1990MaCom..55..355B, doi : 10.2307/2008811 , JSTOR 2008811
^ Jaeschke, Gerhard (1993), "Sobre pseudoprimos fuertes para varias bases", Mathematics of Computation , 61 (204): 915–926, doi : 10.2307/2153262 , JSTOR 2153262
^ Jiang, Yupeng; Deng, Yingpu (2014). "Pseudoprimos fuertes para las primeras ocho bases de primos". Matemáticas de la computación . 83 (290): 2915–2924. doi : 10.1090/S0025-5718-2014-02830-5 . S2CID 33599405.
^ Sorenson, Jonathan; Webster, Jonathan (2015). "Pseudoprimos fuertes hasta doce bases primas". Matemáticas de la computación . 86 (304): 985–1003. arXiv : 1509.00864 . Código Bibliográfico :2015arXiv150900864S. doi :10.1090/mcom/3134. S2CID 6955806.
^ ab Caldwell, Chris. "Encontrar primos y demostrar primalidad — 2.3: Primalidad probable fuerte y una prueba práctica". The Prime Pages . Consultado el 24 de febrero de 2019 .
^ Zhang, Zhenxiang y Tang, Min (2003), "Encontrar pseudoprimos fuertes para varias bases. II", Matemáticas de la computación , 72 (44): 2085–2097, Bibcode :2003MaCom..72.2085Z, doi : 10.1090/S0025-5718-03-01545-X
^ Sloane, N. J. A. (ed.). "Secuencia A014233 (Número impar más pequeño para el cual la prueba de primalidad de Miller-Rabin en bases <= n-ésimo primo no revela compenetración)". La enciclopedia en línea de secuencias de números enteros . Fundación OEIS.
^ Izykowski, Wojciech. «Variantes deterministas de la prueba de primalidad de Miller-Rabin» . Consultado el 24 de febrero de 2019 .
^ Alford, WR ; Granville, A. ; Pomerance, C. (1994), "Sobre la dificultad de encontrar testigos fiables", Algorithmic Number Theory (PDF) , Lecture Notes in Computer Science, vol. 877, Springer-Verlag, págs. 1–16, doi :10.1007/3-540-58691-1_36, ISBN 978-3-540-58691-3
^ Robert Baillie; Samuel S. Wagstaff, Jr. (octubre de 1980). "Lucas Pseudoprimes" (PDF) . Matemáticas de la computación . 35 (152): 1391–1417. doi : 10.1090/S0025-5718-1980-0583518-6 . MR 0583518.
^ Burthe Jr., Ronald J. (1996), "Investigaciones adicionales con la prueba del primo probable fuerte" (PDF) , Matemáticas de la computación , 65 (213): 373–381, Bibcode :1996MaCom..65..373B, doi : 10.1090/S0025-5718-96-00695-3

Enlaces externos

La implementación del algoritmo de Wikibook tiene una página sobre el tema: Pruebas de primalidad

Weisstein, Eric W. "Prueba de pseudoprime fuerte de Rabin-Miller". MundoMatemático .
Implementación interactiva en línea de la variante determinista (recorriendo el algoritmo paso a paso)
Subprograma (alemán)
Prueba de primalidad de Miller-Rabin en C#
Prueba de primalidad de Miller-Rabin en JavaScript utilizando aritmética de precisión arbitraria