Algoritmo para factorizar RSA:
Hola, buenas tardes.
Antes de exponer el asunto principal quiero decir que no soy un profesional ni de las matemáticas ni de la criptografía, solo un matemático aficionado, y como tal, desde que en los años ochenta en el instituto conocí los números primos he seguido de cerca cualquier investigación al respecto incluida la aplicación de éstos a la criptografía.
Paso a detallar el sistema que he seguido para acotar la búsqueda de la factorización aplicada a los rsa.
- -- --- ----- ------- ----------- ------------- -----------------
Tenemos un número rsa, llamémosle n, que es producto de dos números primos desconocidos p y q. p*q=n con p<q.
Dado que es un prodcuto podemos hallar un número m tal que p<m<q, siendo m la media geométrica de p y q, es decir m=[raíz(n)] (los corchetes indican que el contenido ha de ser un número entero).
Ya tenemos una cota máxima m para empezar la búsqueda, pero sería todavía muy dura esa búsqueda, así que trato de hallar p' y q' tal que: p'<p<m<q<q'.
Para calcular p' y q' hago lo siguiente: r=e^(1/raíz(LN(m)). Y p'=[m/r] y q'=[m*r].
Así tenemos p'<p<m<q<q'.
Buscando sólo los primos entre p' y m hallaremos q, q=n/p.
Aún me queda investigar si esta fórmula es válida para p y q muy distantes entre sí, pero funciona en p' y q' cuando log(pi(m)/(pi(m)-pi(p')))<=3. (log; es el logaritmo decimal). (pi(x) es el contador de primos, pi(x)=x/ln(x).
¿Es una buena aproximación para resolver el problema de la facrorización rsa?.
Crear cuenta