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/2k, 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 bt
(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 bt
(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:
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 *)
(* 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];
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}]
