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 determinado sea primo , similar a la prueba de primalidad de Fermat y la prueba de primalidad de Solovay-Strassen .

Es de importancia histórica en la búsqueda de una prueba de primalidad determinista de tiempo polinomial . Su variante probabilística sigue siendo ampliamente utilizada 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 depende de la hipótesis extendida de Riemann no probada . ^[1] Michael O. Rabin lo 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 se cumple para valores primos, se cumple 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 número entero a , llamado base , que es coprimo de 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 al verificar 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 número 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 para basar 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 fuerte probable de la base a , entonces n es definitivamente compuesto, y a se considera 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, no obstante, ser un primo probable fuerte para basar a , en cuyo caso se llama pseudoprimo fuerte , y a es un mentiroso fuerte .

Opciones de bases

Afortunadamente, ningún número compuesto es un pseudoprimo fuerte para todas las bases al mismo tiempo (al contrario de la prueba de primalidad de Fermat para la cual existen pseudoprimos de Fermat para todas las bases: los números de Carmichael ). Sin embargo, no se conoce ninguna 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 (consulte la sección Prueba de Miller a continuación).

Otra solución es escoger 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 (consulte 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}

Tenga en cuenta 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 $n$ arbitrariamente grande , elegir bases al azar es esencial, 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 es generalmente bastante grande en comparación con las bases. Esto proporciona pruebas deterministas muy rápidas para n lo suficientemente pequeño (consulte la sección Pruebas contra pequeños conjuntos 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, aplicado aquí con el polinomio X ² − 1 sobre el campo finito Z / n Z , del hecho más general de que un polinomio sobre algún campo no tiene más raíces que su grado (este teorema se deriva de la existencia de una división euclidiana para polinomios ). A continuación se presenta una prueba más elemental. Supongamos 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 el producto ( x − 1)( x + 1) . Según el lema de Euclides , dado que n es primo, divide 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 con base en a .

Prueba

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

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

Cada término de la secuencia es una raíz cuadrada del término anterior. Dado que el primer término es congruente con 1, el segundo término es una raíz cuadrada de 1 módulo n . Según el lema anterior , es congruente con 1 o −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, cualquiera 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},\dots,a^{2d},a^{d}$

Ejemplo

Supongamos que deseamos determinar si es primo. Escribimos , para que tengamos . Seleccionamos aleatoriamente un número tal que . $n=221$ $n-1{\text{ como }}2^{2}\times 55$ $s=2{\text{ y }}d=55$ $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{. Desde }}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 221 es primo o 174 es un fuerte mentiroso para 221. Probamos con otro aleatorio , esta vez eligiendo : $220\equiv -1{\text{ mod }}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 fuerte mentiroso. Tenga en cuenta 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 para elegir el valor de a , consulte Pruebas contra pequeños conjuntos 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 #1 : n > 2, un entero impar que se probará para determinar su primalidad Entrada #2 : k , el número de rondas de prueba a realizar Salida : “ compuesto ” si se encuentra 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 ← aleatorio(2, n − 2) # n es siempre un primo probable a base 1 y n − 1 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 “ probablemente primo ”

Complejidad

Utilizando 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 determinar la primalidad y k es el número de rondas realizadas; por tanto, este es un algoritmo eficiente de tiempo polinomial. La multiplicación basada en FFT ( algoritmo Harvey-Hoeven ) puede disminuir 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. Cuantas más bases se prueben, mejor será la precisión de la prueba. Se puede demostrar que si n es compuesto, entonces como máximo1/4de las bases a son fuertes mentirosos para n . ^[2]^[7] Como consecuencia, si n es compuesto, ejecutar k iteraciones de la prueba de Miller-Rabin declarará que n probablemente sea primo con una probabilidad como máximo de 4 ^{− k} .

Esta 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 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 desaparece a medida que consideramos valores más grandes de n . ^[8] Por lo tanto, el caso promedio tiene una precisión mucho mayor que 4 ^{− k} , un hecho que puede explotarse para generar números primos probables (ver más abajo). Sin embargo, no se debe confiar en estos 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, sólo se puede confiar en el límite de error del peor de los casos de 4 ^{− k .}

La medida de error anterior es la probabilidad de que un número compuesto sea declarado como 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 primo probable fuerte sea en realidad 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 falsos negativos ). Al eliminar la parte izquierda del denominador , obtenemos 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 sólo con la medida de error analizada 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 ya hemos dicho, esta distribución está controlada por un adversario criptográfico, por lo que es desconocido, por lo que no podemos deducir mucho al respecto . Sin embargo, en el caso de que utilicemos la prueba de Miller-Rabin para generar números primos (ver más abajo), la distribución la elige el propio generador, por lo que podemos aprovechar este resultado. $\Pr(\lnot P\mid M\!R_{k})$

Variantes deterministas

prueba de molinero

El algoritmo de Miller-Rabin puede volverse determinista probando todos los valores posibles de a por debajo de cierto límite. Tomar n como límite implicaría $O(n)$ pruebas, 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 reducir el límite tanto como sea posible manteniendo la confiabilidad de la prueba.

Si el número probado n es compuesto, los fuertes mentirosos coprimos de 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 testigo de la composición de n . Asumiendo la veracidad 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 cual ya fue observado por Miller. ^[1] La constante involucrada en la notación O grande fue reducida a 2 por Eric Bach . ^[10] Esto conduce al siguiente algoritmo de prueba de primalidad, conocido como prueba de Miller , que es determinista suponiendo el GRH:

Entrada : n > 2, un entero impar cuya primalidad se va a comprobar 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 es necesario todo el poder de la hipótesis generalizada de Riemann para garantizar la exactitud de la prueba: como tratamos con subgrupos de índice par , basta con asumir la validez de GRH para caracteres cuadráticos de Dirichlet . ^[7]

El tiempo de ejecución del algoritmo es, en la notación O suave , $Õ((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 mientras se corre mucho más rápido. También es más lento en la práctica que los métodos de prueba comúnmente utilizados, como APR-CL y ECPP , que dan resultados que no se basan en suposiciones no probadas. Para fines teóricos que requieren un algoritmo de tiempo polinomial determinista, fue reemplazado por la prueba de primalidad de 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 todo $a < 2(ln n) 2$ , ya que se sabe que son suficientes conjuntos mucho más pequeños de testigos potenciales. Por ejemplo, Pomerance, Selfridge, Wagstaff ^[4] y Jaeschke ^[11] han verificado que

si n < 2.047, basta con 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, basta probar a = 2, 3 y 5;
si n < 3.215.031.751, basta probar a = 2, 3, 5 y 7;
si n < 4.759.123.141, basta con probar a = 2, 7 y 61;
si n < 1.122.004.669.633, basta con probar a = 2, 13, 23 y 1662803;
si n < 2.152.302.898.747, basta con probar a = 2, 3, 5, 7 y 11;
si n < 3.474.749.660.383, basta con 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 diferentes métodos 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 superiores a 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 necesitan menos bases) que los mostrados anteriormente. ^[14]^[15]^[16]^[17] Dan 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 valores b 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 testimonio 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 tenga 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 con base a pero no un primo probable fuerte con base a . ^[19]^{: 1402}

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

ya que $x 2 \equiv 1 (mod n)$ , sabemos que n divide $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 norte = AB ). Por lo tanto, si el objetivo es la factorización, estos cálculos de mcd se pueden insertar en el algoritmo con un pequeño costo computacional adicional. Esto lleva al siguiente pseudocódigo, donde se resalta el código agregado o modificado:

Entrada #1 : n > 2, un entero impar que se probará para determinar su primalidad Entrada #2 : k , el número de rondas de prueba a realizar Salida : (" múltiplo de ", m ) si se encuentra un factor no trivial m de n , “ compuesto ” si se determina 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 ← aleatorio(2, n − 2) # n es siempre un primo probable a base 1 y n − 1  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  return (“ 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 son pseudoprimos con 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 una base pseudoprime 2, pero no una base pseudoprime fuerte 2. 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 más frecuencia, también se pueden aplicar las mismas ideas a las raíces cuadradas de −1 (o cualquier otro número). Esta estrategia se puede implementar aprovechando el conocimiento de rondas anteriores de la prueba de Miller-Rabin. En esas rondas es posible que hayamos identificado un módulo de raíz cuadrada 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 números 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 números primos probables de b bits fuertes (con el conjunto de bits más significativo) es el siguiente:

Entrada #1 : b , el número de bits del resultado Entrada #2 : k , el número de rondas de prueba a realizar Salida : un primo probable fuerte n

mientras que 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 ” , luego  devuelva  n

Complejidad

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

Cuando 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 dibujamos enteros impares uniformemente en el rango [2 ^{b −1} , 2 ^b −1], entonces 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 de los casos de cada prueba de Miller-Rabin (ver anteriormente), el tiempo de funcionamiento esperado del generador con entradas b y k está entonces limitado por $O(k b 4)$ (o $Õ(k b 3)$ usando multiplicación basada en FFT).

Exactitud

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

Utilizando la relación entre las probabilidades condicionales (que se muestra en una sección anterior) y el comportamiento asintótico de (que se muestra 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 b lo 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 propia prueba de Miller-Rabin a menudo tiene un límite de error mucho menor que 4 ^{− k} (ver antes), 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 una k razonable para una precisión deseada.

Uno de estos límites de error es 4 ^{− k} , que se cumple para todo b ≥ 2 (los autores solo lo mostraron 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 de 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 todo 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] (particularmente su Teorema E ) muestra que en realidad descubrió la prueba de Solovay-Strassen.
^ Por ejemplo, en 1995, Arnault da un número compuesto de 397 dígitos para el cual todas las bases inferiores a 307 son fuertes mentirosas; La función Maple informó que este número era primo isprime(), porque implementó la prueba de Miller-Rabin con las bases específicas 2, 3, 5, 7 y 11. ^[5]
^ 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 y pruebas de primalidad de Riemann", 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 para la primalidad de los 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". Revista de Computación Simbólica . 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: celosías, campos numéricos, curvas y criptografía , Cambridge University Press, ISBN 978-0-521-80854-5
^ ab Damgård, I .; Landrock, P. & Pomerance, C. (1993), "Estimaciones de error de caso promedio para la prueba de primo probable fuerte" (PDF) , Matemáticas de la Computación , 61 (203): 177–194, Bibcode :1993MaCom..61.. 177D, doi : 10.2307/2152945, JSTOR 2152945
^ Martín R. Albrecht; Jake Massimo; Kenneth G. Paterson; Juraj Somorovsky (15 de octubre de 2018). Prime and Prejudice: Pruebas de primalidad en condiciones adversas (PDF) . Conferencia ACM SIGSAC sobre seguridad informática y de las comunicaciones 2018. Toronto: Asociación de Maquinaria de Computación . págs. 281–298. doi :10.1145/3243734.3243787.
^ Bach, Eric (1990), "Límites explícitos para pruebas de primalidad y problemas relacionados", Matemáticas de la Computación , 55 (191): 355–380, Bibcode :1990MaCom..55..355B, doi : 10.2307/2008811 , JSTOR 2008811
^ Jaeschke, Gerhard (1993), "Sobre pseudoprimos fuertes para varias bases", Matemáticas de la Computación , 61 (204): 915–926, doi : 10.2307/2153262 , JSTOR 2153262
^ Jiang, Yupeng; Deng, Yingpu (2014). "Pseudoprimos fuertes para las primeras ocho bases principales". 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 a doce bases principales". Matemáticas de la Computación . 86 (304): 985–1003. arXiv : 1509.00864 . Código Bib : 2015arXiv150900864S. doi : 10.1090/mcom/3134. S2CID 6955806.
^ ab Caldwell, Chris. "Encontrar números primos y demostrar la primalidad - 2.3: Primalidad probable fuerte y una prueba práctica". Las páginas principales . 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, Nueva Jersey (ed.). "Secuencia A014233 (el número impar más pequeño para el cual la prueba de primalidad de Miller-Rabin en bases <= n-ésima prima no revela composición)". La enciclopedia en línea de secuencias enteras . 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 confiables", Teoría algorítmica de números (PDF) , Lecture Notes in Computer Science, vol. 877, Springer-Verlag, págs. 1 a 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 Pseudoprimos» (PDF) . Matemáticas de la Computación . 35 (152): 1391-1417. doi : 10.1090/S0025-5718-1980-0583518-6 . SEÑOR 0583518.
^ Burthe Jr., Ronald J. (1996), "Más investigaciones con la prueba de 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)
Applet (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