Test de primalidad de Miller-Rabin

El test de primalidad de Miller-Rabin es un test de primalidad, es decir, un algoritmo para determinar si un número dado es primo, similar al test de primalidad de Fermat. Su versión original fue propuesta por G. L. Miller, se trataba de un algoritmo determinista, pero basado en la no demostrada hipótesis generalizada de Riemann;^[1] Michael Oser Rabin modificó la propuesta de Miller para obtener un algoritmo probabilístico que no utiliza resultados no probados.^[2]

Conceptos matemáticos

De forma similar a las pruebas Fermat y Solovay-Strassen, la prueba de primalidad de Miller-Rabin comprueba si una propiedad específica, que se sabe que es verdadera para los números primos, se satisface para el número a prueba.

Probables primos fuertes

Dado un entero impar n > 2, escribimos n como 2^s⋅d + 1 donde s y d son enteros positivos y d es impar. Sea a un número entero tal que 0 < a < n. Entonces, diremos que n es probable primo fuerte para la base a si se cumple alguna de las siguientes relaciones de congruencia:

• ${\displaystyle a^{d}\equiv 1{\pmod {n}}}$;
• ${\displaystyle a^{2^{r}\cdot d}\equiv -1{\pmod {n}}}$ para algún 0 ≤ r < s.

La idea detrás del test de Miller-Rabín es que cuando n es un primo impar, pasa el test debido a dos resultados:

• por el pequeño teorema de Fermat, ${\displaystyle a^{n-1}\equiv 1{\pmod {n}}}$ (esta propiedad por sí sola es una noción más débil probable primo débil para la base a, sobre la cual está basado el test de primalidad de Fermat);
• las únicas raíces cuadradas del 1 módulo n son 1 y −1.

Por contraposición, si n no es un probable primo fuerte para alguna base a, entonces n es compuesto y a es llamado un testigo de la propiedad de que n es compuesto.

Sin embargo, esta propiedad no es una caracterización exacta de los números primos. Si n es compuesto, puede haber una base a para la cual n sea probable primo fuerte, en cuyo caso se llama un pseudoprimo fuerte y a se lo denomina un mentiroso fuerte.

El test probabilístico de Miller-Rabin se basa en la comprobación para diferentes bases de que un número dado es probable primo fuerte.

Elección de bases

Afortunadamente, ningún número compuesto es un pseudoprimo fuerte para todas las bases al mismo tiempo. 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 determinista es una variante más eficiente de esto.

Otra solución es elegir una base al azar. Esto produce una rápida prueba probabilística. 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, mayor que 0.75. 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. En esto consiste el test probabilístico de Miller-Rabin. El número de bases a probar no depende de n.

Para hacer el test a un 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 1, 2, …, n−1.^[4]

Demostraciones

Aquí una demostración de que cuando n es un primo impar, las únicas raíces cuadradas de 1 módulo n son 1 y −1.

Demostración

Sea x tal que ${\displaystyle x^{2}\equiv 1{\pmod {n}}}$, luego ${\displaystyle x^{2}-1\equiv 0{\pmod {n}}}$, como ${\displaystyle x^{2}-1=(x-1)(x+1)}$, obtenemos ${\displaystyle (x-1)(x+1)\equiv 0{\pmod {n}}}$. Esto quiere decir que ${\displaystyle n|(x-1)(x+1)}$. Como n es primo, ${\displaystyle n|x-1}$ o ${\displaystyle n|x+1}$, es decir ${\displaystyle x\equiv 1{\pmod {n}}}$ o ${\displaystyle x\equiv -1{\pmod {n}}}$.

Aquí una demostración de que si n es un primo impar, entonces n es probable primo fuerte para cualquier base a.

Demostración

Consideremos la sucesión ${\displaystyle a^{2^{s}\cdot d},a^{2^{s-1}\cdot d},\dots ,a^{2d},a^{d}}$ y observemos que cada término de la sucesión es el cuadrado del siguiente. Por el teorema de Fermat ${\displaystyle a^{2^{s}\cdot d}=a^{n-1}\equiv 1{\pmod {n}}}$. Luego ${\displaystyle (a^{2^{s-1}\cdot d})^{2}\equiv 1{\pmod {n}}}$ y por lo tanto ${\displaystyle a^{2^{s-1}\cdot d}}$ es una raíz cuadrada de 1 módulo n. Por lo anterior obtenemos que ${\displaystyle a^{2^{s-1}\cdot d}\equiv \pm 1{\pmod {n}}}$. Si ${\displaystyle a^{2^{s-1}\cdot d}\equiv -1{\pmod {n}}}$, obtenemos el resultado. En caso contrario ${\displaystyle a^{2^{s-1}\cdot d}\equiv 1{\pmod {n}}}$, luego ${\displaystyle (a^{2^{s-2}\cdot d})^{2}\equiv 1{\pmod {n}}}$ y por lo tanto ${\displaystyle a^{2^{s-2}\cdot d}}$ es una raíz cuadrada de 1 módulo n y en consecuencia ${\displaystyle a^{2^{s-2}\cdot d}\equiv \pm 1{\pmod {n}}}$. Iterando el razonamiento anterior concluimos que alguno de los términos de la sucesión ${\displaystyle a^{2^{r}\cdot d}}$ es congruente a -1 módulo n o bien todos los términos son congruentes a 1, en particular ${\displaystyle a^{d}\equiv 1{\pmod {n}}}$, con lo cual n resulta ser probable primo fuerte.

Test 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 (k es el número de rondas), mayor precisión tendrá el resultado.

Pseudocódigo estilo Python:

def test_Miller_Rabin(n: int, k: int) -> bool:
    s, d = satisfacen n = 2**s * d + 1, d impar
    repetir k veces:
        a = entero al azar entre 2 y n-1
        fpp = False # fuertemente primo en base a
        if 1 == a**d % n:
            fpp = True
        else:
            r = 0
            while r  <= s and fpp == False:
                if n - 1 == a**(2**r * d) % n:
                    fpp = True
         if fpp == False: # si no pasa la prueba
            return False
    # si pasó las k pruebas
    return True

Complejidad

El tiempo de ejecución de este algoritmo es ${\displaystyle O(k\ln ^{3}n)}$, donde n es el número testeado y k es el número de rondas realizadas; por lo tanto, este es un algoritmo eficiente, de tiempo polinomial respecto a la cantidad de dígitos de n. La multiplicación basada en transformada rápida de Fourier puede reducir el tiempo de ejecución a ${\displaystyle O(k\ln ^{2}(n)\ln(n)\ln(\ln \ln n))}$.

Fiabilidad del test

Debido a su baja probabilidad de fallo, es el test más utilizado en la práctica, a la hora de aplicaciones en criptografía de clave pública.^[5]

Se puede demostrar que un número que pasa una prueba de ser probable primo fuerte tiene una probabilidad de 3/4 de ser primo. Luego, que la probabilidad de que un número compuesto pase h iteraciones del test con bases escogidas al azar es menor a ${\displaystyle {\tfrac {1}{4^{h}}}}$. En la práctica, la probabilidad parece ser mucho menor, según un artículo de Damgård, Landrock y Pomerance.^[6]

Asumiendo correcta la hipótesis generalizada de Riemann, se puede demostrar que, n es probable primo fuerte para a tal que ${\displaystyle 0\leq a\leq 2\ln ^{2}n}$ entonces n es un número primo. Con esto se tiene un test determinístico de primalidad de costo ${\displaystyle O(\ln ^{4}n)}$.