Prueba de primalidad de Miller-Rabin

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Prueba de primidad

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 la prueba de primalidad de Solovay-Strassen.

Tiene 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 sencillas 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 corrección se basa en la hipótesis de Riemann extendida no probada. Michael O. Rabin lo modificó para obtener un algoritmo probabilístico incondicional en 1980.

Conceptos matemáticos

Al igual que 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 los valores primos, se cumple para el número que se está probando.

Primos probables fuertes

La propiedad es la siguiente. Para un entero impar dado n > 2, escribamos n − 1 como 2^sd donde s es un número entero positivo y d es un número 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 en base a si se cumple una de estas relaciones de congruencia:

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

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, $a^{{n-1}}equiv 1{pmod {n}}$ (esta propiedad solo define la noción más débil de probable primo para basar un, en el que se basa la prueba Fermat);
las únicas raíces cuadradas de 1 modulo 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 no obstante ser un primo probable fuerte para la base a, en cuyo caso se llama un 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 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 (consulte 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 (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 de forma independiente como sea necesario para lograr dicha tasa. Esta es la prueba de Miller-Rabin. El número de bases a intentar no depende de n. 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.

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 el Misma razón. Es por eso que $a$ se eligen aleatoriamente en el intervalo $1 < a < n - 1$ .

Para probar $n$ arbitrariamente grandes, es esencial elegir bases al azar, ya que no conocemos la distribución de testigos y fuertes mentirosos entre los números 2, 3, …, $n - 2$ .

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

Pruebas

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

Prueba

Ciertamente 1 y −1, cuando modulo cuadrado n, siempre rendimiento 1. Queda por demostrar que no hay otras raíces cuadradas de 1 modulo n. Este es un caso especial, aquí aplicado con el polinomio X² − 1 sobre el campo finito Z/nZ, 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). Aquí sigue una prueba más elemental. Supongamos que x es una raíz cuadrada de 1 modulo n. Entonces:

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

En otras palabras, n divide el producto ()x − 1)x + 1). Por la lema de Euclides, desde n es primo, divide uno de los factores x − 1 o x + 1, implicando que x es congruente con 1 o −1 modulo n.

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

Prueba

Si n es una prima extraña y escribimos n − 1 = 2^sd Donde s es un entero positivo y d es un extraño entero positivo, por el pequeño teorema de Fermat:

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

Cada término de la secuencia ${displaystyle a^{2^{s}d},a^{2^{s-1}d},dotsa^{2d},a^{d}}$ es una raíz cuadrada del término anterior. Puesto que el primer término es congruente con 1, el segundo término es una raíz cuadrada de 1 modulo n. Por el lema anterior, es congruente con 1 o −1 modulo n. Si es congruente con −1, estamos acabados. 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 ellos son congruentes con 1, y en particular el último término, a^d, lo es.

Ejemplo

Supongamos que deseamos determinar si n = 221 es primo. Escribimos n − 1 como 2² × 55, entonces que tenemos s = 2 y d = 55. Seleccionamos aleatoriamente un número a tal que 2 ≤ a ≤ n−2, digamos a = 174. Procedemos a calcular:

a^2⁰d mod n = 174⁵⁵ mod 221 = 47 ل 1, n − 1
a^2¹d mod n = 174¹¹⁰ mod 221 = 220 = n − 1.

Dado que 220 ≡ −1 mod n, 221 es primo o 174 es un fuerte mentiroso para 221. Probamos otro a, esta vez eligiendo a = 137:

a^2⁰d mod n = 137⁵⁵ mod 221 = 188 ل 1, n − 1
a^2¹d mod n = 137¹¹⁰ mod 221 = 205 ل n − 1.

Por lo tanto, 137 es un testigo de la composición de 221, y 174 fue, de hecho, un gran 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.

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.

Entrada #1: n > 2, un número extraño para ser probado para la primalidad
Entrada #2: k, el número de rondas de pruebas para realizar
Producto: “composite” si n es encontrado para ser compuesto, "probablemente la primera” de otro modo

Deja s " 0 " d extraño 0 tal que n − 1 = 2^sd # Al factorar los poderes de 2 de n − 1repetición k veces:
 a ← random(2, n − 2) n es siempre un principio probable para la base 1 y n − 1
 x ← a^d mod n repetición s veces:
 Sí. ← x² mod n si Sí. = 1 y x ل 1 y x ل n − 1 entonces # raíz cuadrada notrivial de 1 modulo n retorno “composite”
 x ← Sí. si Sí. ل entonces retorno “composite”
retorno “probablemente la primera”

Complejidad

Al elevar al cuadrado repetidamente, 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 en tiempo polinomial. La multiplicación basada en FFT (algoritmo Harvey-Hoeven) puede reducir el tiempo de ejecución a $O(k log 2 n registro registro n) = Õ(k registro 2 n)$ .

Precisión

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 a se prueben, mejor será la precisión de la prueba. Se puede demostrar que si n es compuesto, entonces como mucho 1/4 de las bases a son fuertes mentirosas para n. Como consecuencia, si n es compuesto, ejecutar k iteraciones de la prueba de Miller-Rabin declarará n probablemente primo con una probabilidad máxima 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 n compuesto, el conjunto de mentirosos fuertes para n es un subconjunto de el conjunto de los mentirosos de Euler para n, y para muchos n, el subconjunto es propio.

Además, para valores grandes de n, la probabilidad de que un número compuesto sea declarado probablemente primo suele ser 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. Por lo tanto, el caso promedio tiene una precisión mucho mejor que 4^−k, un hecho que se puede explotar para generar primos probables (ver más abajo). Sin embargo, no se debe confiar en estos límites de error mejorados para verificar números 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. 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 fuerte principio probable después de k rondas de pruebas; en palabras matemáticas, es la probabilidad condicional ${displaystyle Pr(M!R_{k}mid lnot P)}$ Donde P es el evento que el número que se está probando es primo, y MR_k es el evento que pasa la prueba Miller-Rabin con k rondas. A menudo nos interesa la probabilidad condicional inversa ${displaystyle Pr(lnot Pmid M!R_{k})}$ : la probabilidad de que un número que ha sido declarado como un fuerte principio probable es de hecho compuesto. Estas dos probabilidades están relacionadas por la ley de Bayes:

{displaystyle {begin{aligned}Pr(lnot Pmid M!R_{k})&={frac {Pr(lnot Pland M!R_{k})}{Pr(lnot Pland M!R_{k})+Pr(Pland 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 usando 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:

<math alttext="{displaystyle Pr(lnot Pmid M!R_{k})Pr()¬ ¬ P▪ ▪ MRk).Pr()MRk▪ ▪ ¬ ¬ P)()1Pr()P)− − 1){displaystyle Pr(lnot Pmid M!R_{k}) Pr(M!R_{k}mid lnot P)left({tfrac {1}{Pr(P)}}-1right)}<img alt="{displaystyle Pr(lnot Pmid M!R_{k})

De ahí que esta probabilidad condicional esté relacionada no sólo con la medida de error discutida anteriormente, que está ligada por 4^−k— pero también a la distribución de probabilidad del número de entrada. En el caso general, como se dijo anteriormente, esta distribución es controlada por un adversario criptográfico, por lo tanto desconocido, por lo que no podemos deducir mucho sobre ${displaystyle Pr(lnot Pmid M!R_{k})}$ . Sin embargo, en el caso cuando usamos la prueba Miller-Rabin para generar primos (ver abajo), la distribución es elegida por el propio generador, para que podamos explotar este resultado.

Variantes deterministas

Prueba de Miller

El algoritmo de Miller-Rabin se puede hacer determinista probando todos los a posibles por debajo de cierto límite. Tomar n como límite implicaría $O(n)$ ensayos, por lo que 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 y mantener la confiabilidad de la prueba.

Si el número probado n es compuesto, los mentirosos fuertes a coprime a n están contenidos en un subgrupo propio del grupo (Z/nZ)*, lo que significa que si probamos todos los a de un conjunto que genera (Z/nZ)*, uno de ellos debe estar fuera de dicho subgrupo, por lo que debe ser testigo de la composición de n. Asumiendo la verdad de la hipótesis de Riemann generalizada (GRH), se sabe que el grupo es generado por sus elementos menores que $O((ln n) 2)$ , que ya señaló Miller. La constante involucrada en la notación Big O fue reducida a 2 por Eric Bach. Esto conduce al siguiente algoritmo de prueba de primalidad determinista, conocido como prueba de Miller:

Input: n > 2, un número extraño para ser probado para la primalidad
Producto: “composite” si n es compuesto, “primo” de otro modo

Deja s " 0 " d extraño 0 tal que n − 1 = 2^sd # Al factorar los poderes de 2 de n − 1para todos a dentro el rango [2, min(n − 2, ⌊2(ln n)²⌋)]:
 x ← a^d mod n repetición s veces:
 Sí. ← x² mod n si Sí. = 1 y x ل 1 y x ل n − 1 entonces # raíz cuadrada notrivial de 1 modulo n retorno “composite”
 x ← Sí. si Sí. ل entonces retorno “composite”
retorno “primo”

No se necesita toda la potencia de la hipótesis de Riemann generalizada para garantizar la corrección de la prueba: como tratamos con subgrupos de índice par, basta con asumir la validez de GRH para caracteres cuadráticos de Dirichlet.

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

La prueba de Miller no se usa 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 ejecuta 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 requerían un algoritmo de tiempo polinomial determinista, fue reemplazado por la prueba de primalidad AKS, que tampoco se basa en suposiciones no comprobadas.

Pruebas contra pequeños conjuntos de bases

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

si n ■ 2,047, es suficiente para probar a = 2;
si n Identificado 1,373,653, es suficiente para probar a = 2 y 3;
si n 080,191, es suficiente para probar a = 31 y 73;
si n 25,326,001, es suficiente para probar a = 2, 3, y 5;
si n 3,215,031,751, es suficiente para probar a = 2, 3, 5 y 7;
si n 4,759,123,141, es suficiente para probar a = 2, 7, y 61;
si n ### 1,122,004,669,633, it is enough to test a = 2, 13, 23, y 1662803;
si n - 2,152,302,898,747, es suficiente para probar a = 2, 3, 5, 7, y 11;
si n 3,474,749,660,383, es suficiente para probar a = 2, 3, 5, 7, 11, y 13;
si n Identificado 341,550,071,728,321, es suficiente para probar a = 2, 3, 5, 7, 11, 13, y 17.

Usando el trabajo de Feitsma y Galway enumerando todos los pseudoprimos de base 2 en 2010, esto se amplió (ver OEIS: A014233), y el primer resultado se muestra más tarde usando diferentes métodos en Jiang y Deng:

si n 3.825,123,056,546,413,051, es suficiente para probar a = 2, 3, 5, 7, 11, 13, 17, 19, y 23.
si n 18,446,744,073,709,551,616 = 2⁶⁴, es suficiente para probar a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 y 37.

Sorenson y Webster verifican lo anterior y calculan resultados precisos para estos resultados de más de 64 bits:

si n ■ 318,665,857,834,031,151,167,461, es suficiente para 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 para 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 que se muestran arriba. Brindan 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 de b para números de b-bit). 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)$ . También argumentan heurísticamente que el número más pequeño w tal que cada número compuesto debajo de n tiene un testigo de composición menor que w debería ser de orden $Θ(registro n registro registro 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 la base a pero no un primo probable fuerte de la base a.

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

desde entonces $x 2 (modelo) n)$ , sabemos que n divideciones $x 2 - 1 = x - 1) x + 1)$ ;
desde entonces $x \pm 1 (modelo) n)$ , sabemos que n no divide $x - 1$ ni $x + 1$ .

De esto deducimos que $A = mcd(x - 1, n)$ y $B = mcd(x + 1, n)$ no son triviales (no necesariamente primo) factores 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 gcd se pueden insertar en el algoritmo con un costo computacional adicional pequeño. Esto conduce al siguiente pseudocódigo, donde se resalta el código agregado o modificado:

Entrada #1: n > 2, un número extraño para ser probado para la primalidad
Entrada #2: k, el número de rondas de pruebas para realizar
Producto: (“múltiples, m) si un factor notrivial m de n se encuentra,“composite” si n se encuentra de otro modo compuesto,
“probablemente la primera” de otro modo

Deja s " 0 " d extraño 0 tal que n − 1 = 2^sd # Al factorar los poderes de 2 de n − 1
repetición k veces:
 a ← random(2, n − 2) # n es siempre un principio probable para la base 1 y n − 1 x ← a^d mod n repetición s veces:
 Sí. ← x² mod n si Sí. = 1 y x ل 1 y x ل n − 1 entonces # raíz cuadrada notrivial de 1 modulo n retorno (“múltiples, gcd(x, 1, n) x ← Sí. si Sí. ل entonces retorno “composite”
retorno “probablemente la primera”

Este no es un algoritmo de factorización probabilística porque solo es capaz de encontrar factores para números n que son pseudoprimos a la base a (en en otras palabras, para números n tales que $a n -1 \equiv 1 módulo 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 pseudoprima 2, pero no una fuerte base pseudoprima 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 más a menudo, 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 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 contra R: si x no es ni R ni n −R, luego $gcd(x - R, n)$ y $gcd(x + R, n)$ no son triviales factores de n.

Generación de primos probables

La prueba de Miller-Rabin se puede usar 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 sacar un número primo). El pseudocódigo para generar primos probables fuertes de b bits (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 pruebas para realizar
Producto: un fuerte principio probable nmientras Cierto:
elegir un entero extraño n en el rango [2^b−1, 2^b−1
 si la prueba Miller-Rabin con entradas n y k devuelve “probablemente la primera” entonces retorno n

Complejidad

Por supuesto, el peor de los casos es infinito, ya que el bucle exterior puede nunca terminar, pero eso sucede con la probabilidad cero. Según la distribución geométrica, el número esperado de sorteos es ${displaystyle {tfrac {1}{Pr(M!R_{k})}}}$ (reutilizando notaciones de antes).

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 dibujamos enteros impares uniformemente en el rango [2^b−1, 2^b−1], entonces obtenemos:

Pr(P)={frac {pi left(2^{b}right)-pi left(2^{b-1}right)}{2^{b-2}}}}" xmlns="http://www.w3.org/1998/Math/MathML">Pr()MRk)■Pr()P)=π π ()2b)− − π π ()2b− − 1)2b− − 2{displaystyle Pr(M!R_{k})}Pr(P)={frac {pi left(2^{b}right)-pi left(2^{b-1}right)}{2^{b-2}}}}}}}}}}}Pr(P)={frac {pi left(2^{b}right)-pi left(2^{b-1}right)}{2^{b-2}}}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7ad3d4951590ecd4f1ef58acc8032b9e75e352c4" style="vertical-align: -2.338ex; width:39.133ex; height:6.676ex;"/>

donde π es la función de conteo de números 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:

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

{displaystyle {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 caso más desfavorable 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⁴) (o $Õ(k b 3)$ utilizando la multiplicación basada en FFT).

Precisión

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

Usando la relación entre probabilidades condicionales (mostradas en una sección anterior) y el comportamiento asintotico de ${displaystyle Pr(P)}$ (shown just before), esta medida de error se puede dar un límite superior grueso:

<math alttext="{displaystyle Pr(lnot Pmid M!R_{k})Pr()¬ ¬ P▪ ▪ MRk).Pr()MRk▪ ▪ ¬ ¬ P)()1Pr()P)− − 1)≤ ≤ 4− − k()In⁡ ⁡ 22b− − 1+O()b− − 1)).{displaystyle Pr(lnot Pmid M!R_{k}) Pr(M!R_{k}mid lnot P)left({tfrac {1}{Pr(P)}}-1right)leq 4^{-k}left({tfrac {ln 2}{2}}b-1+{mathcal {O}left(b^{-1}right)right). }<img alt="{displaystyle Pr(lnot Pmid M!R_{k})

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

Usando el hecho de que la prueba de Miller-Rabin en sí misma a menudo tiene un límite de error mucho más pequeño que 4^−k (ver antes), Damgård, Landrock y Pomerance derivaron varias límites de error para el generador, con varias clases de parámetros b y k. Estos límites de error permiten que un implementador elija un k razonable para la 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). Nuevamente, este límite simple se puede mejorar para valores grandes de b. Por ejemplo, otro límite derivado por los mismos autores es:

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

que se cumple para todo b ≥ 21 y k ≥ b/4. Este límite es menor que 4^−k tan pronto como b ≥ 32.

Contenido relacionado

Más resultados...