Probabilística

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”

 


Solovay-Strassen.

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 par números pequeños
Prueba Solovay-Strassen en Java para números pequeños

 

 

 

Miller-Rabin.

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.

 

Prueba Miller-Rabin en Java
Prueba Miller-Rabin en Java

Existen otro menos conocidos que abordaremos posteriormente.

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

13 − 12 =