Para números muy grandes, como los usados en sistemas criptográficos RSA que llegan a tener tamaños de entre 1.024 y 2.048 bits, no es viable, en un tiempo razonable, tratar de factorizar un número para saber si es o no primo, por ello existen métodos probabilísticos que nos pueden decir con un cierto grado de certeza si un número es primo o compuesto. Algunos de los mostrados a continuación, si les aplicamos la hipótesis extendida de Riemann, pueden transformarse en deterministas (Monte Carlo, Solovay-Strassen, Miller-Rabin).
Fermat.
El teorema de Fermat afirma que si n es un primo y a es cualquier número entero en el intervalo, 1 ≤ a ≤ n-1, entonces an-1 ≡ 1 (mod n). Si encontramos un número a en el intervalo que haga la equivalencia falsa, demostraremos que n es compuesto.
El algoritmo puede ser el siguiente:
n = nº a identificar
t = nº de comprobaciones
para n ≥3 y t ≥ 1.
Fermat(n,t)
Desde 1 hasta t hacer
Tomamos un nº aleatorio 2 ≤ a ≡ n ≤ 2.
Calculamos r = an-1 ≡ 1 (mod n)
Si r = 1 devolvemos “compuesto”.
Fin desde
Devolvemos “primo”
Fue desarrollado por Robert M. Solovay y Volker Strassen en 1.977, posteriormente mejorado en 1.982, pero ahora está en desuso por la prueba de Miller-Rabin. La prueba Solovay-Strassen aporta la seguridad de que un número dado es compuesto y en caso contrario, cierta probabilidad de que sea primo. La razón de que este algoritmo sea más costoso en tiempo de computación es debido a que necesita realiar el calculo del símbolo de Jacobi. Tiene un orden de complejidad O(k × log3 n), donde k es el nº de veces que iteramos.
Prueba Solovay-Strassen en Java para números pequeños
Esta prueba está basada en los trabajos que Gari Miller realizó en 1.976 y que Michael Rabin modificó en 1.980. Si el número procesado es compuesto no garantiza con certeza que lo es, el error es inferior a (1/4)4 , por contra, si lo identifica como primo, es primo. Tiene un orden de complejidad O(k × log3 n), donde k es el nº de veces que iteramos.
Existen otro menos conocidos que abordaremos posteriormente.