Test de Primalidad III

  Test de Primalidad de Solovay-Strassen

Supongamos que n es un entero positivo impar, nuestra intención es verificar si n, es primo o compuesto, elegimos k enteros, tal que 0 < b < n aleatorios. Para cada b, primero, calculamos los dos términos de 

si el segundo término, no es congruente módulo n, entonces llegamos a la conclusión de que n es compuesto y paramos el proceso.

En caso contrario, seleccionamos otro valor de b, si la expresión anterior es válida para todos los k aleatorios de b, entonces la probabilidad de que n sea compuesto a pesar de pasar todas las pruebas es de a los sumo de 1/2^k, por lo que este test es de tipo probabilístico, por lo que si n supera el test, a lo sumo podemos concluir que es probablemente primo.

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 trata de un algoritmo determinista, pero basado en la no demostrada hipótesis generalizada de Riemann; Michael Oser Rabin modificó la propuesta de Miller para obtener un algoritmo probabilístico incondicional.

Supongamos que n es un entero impar, del cual queremos saber si es primo o compuesto, sea t un valor impar tal que , la forma de proceder es la siguiente:

Primero calculamos  b^t (mod n), si obtenemos ± 1, entonces concluimos que n pasa el test que lo clasifica como pseudoprimo fuerte, para el valor de b usado, entonces seleccionamos otro valor aleatorio de b.

Posteriormente elevamos al cuadrado la expresión b^t (mod n), y así sucesivamente hasta llegar al valor -1, entonces n pasa el test.

Sin embargo, si nunca obtenemos el valor -1, si alcanzamos

 donde:

entonces n falla el test y deducimos que n es compuesto.

Se puede demostrar que un número compuesto es clasificado "probable primo" en una iteración del algoritmo con una probabilidad inferior a 1/4; de hecho, en la práctica la probabilidad es mucho menor.

En resumen el test es siempre cierto si el número es compuesto, es decir en el caso de obtener una respuesta positiva sobre un número, hay que considerarlo como "posible primo", por lo que como en los diagnóstico médicos es mejor una segunda opinión, es decir usar más de un test de primalidad

El algoritmo para implementar el test de Miller-Rabin lo podeis encontrar en la siguiente dirección:

https://rosettacode.org/wiki/Miller%E2%80%93Rabin_primality_test

 donde lo podeis encontrar en varios lenguajes de programación

os dejo el código correspondiente a Mathematica como función :

MillerRabin[n_, k_] := Module[{d = n - 1, s = 0, test = True},
  (* n es el numero a estudiar y k las iteraciones a realizar*)
  While[Mod[d, 2] == 0, d /= 2; s++] Do[a = RandomInteger[{2, n - 1}];
     x = PowerMod[a, d, n];
    If[x != 1,
     For[r = 0, r < s, r++, If[x == n - 1, Continue[]];
      x = Mod[x*x, n];];
     If[x != n - 1, test = False];];, {k}];
  Print[test]]
(* el problema de este test es que los que no pasan el test no son \
primos, pero los que lo pasan pueden ser cumpuestos *)

Generamos aleatoriamente enteros grandes

numerointeger = RandomInteger [{10^200, 10^201}];
Print ["El número entero aleatorio es ", numerointeger];

 y los podemos comprobar con la funcion que implementa el test :

 MillerRabin[numero entero, 1000] 

Mathematica también implementa el método con la función PrimeQ[numero entero], por lo que :

PrimeQ[numero entero]

Podemos generar números enteros aleatorios y comprobar las dos funciones a ver que tal.

Mathematica también es capaz de generar números primos aleatorios, con la función:

RamdomPrime[{limite inferior,limite superior}]