Criptografia - Algoritmo para factorizar RSA.

   
Vista:

Algoritmo para factorizar RSA.

Publicado por chemary (2 intervenciones) el 27/07/2009 18:44:39
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?.
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder