Digo en teoría porque, como ya he venido insistiendo en esta serie de post, los métodos conocidos y que es posible implementar hasta la fecha no resuelven la factorización del módulo (n) en sus dos factores primos (p y q) en tiempo polinomial y, por tanto, son ineficientes para abordar este problema en un tiempo razonable cuando se trata de números lo suficientemente grandes (ya dije en el post anterior que actualmente se emplea un tamaño para el módulo de 2.048 bits).
En esta ocasión le toca el turno al método de factorización rho de Pollard.
Como siempre utilizaré el ejemplo que vengo usando en esta serie de posts (n = pq = 53 x 997 = 52.841).
Como vemos, en tan sólo 6 iteraciones hemos conseguido factorizar el módulo (52.841) en sus dos factores primos (53 y 997); de forma significativamente más eficiente, en este caso, que con el método de Fermat al que me referí en el post anterior, pero, por lo que voy aprendiendo, no se puede afirmar rotundamente que un método sea más eficiente que otro, sino que esto depende del número concreto a factorizar.
Me pregunto: ¿cuál de estos dos métodos sería más eficiente en el ejemplo que puse en el post anterior en el que los dos factores primos estaban muy cercanos entre sí (n = pq = 991 x 997 = 988.027)?. Asunto que dejo como ejercicio para quien quiera resolverlo (como siempre se admiten conclusiones, etc. en forma de comentario a esta entrada).
En cualquier caso, comentar que se considera que el método de factorización rho de Pollard es eficiente para factorizar números compuestos con factores menores de 1012, lo que está muy por debajo de los utilizados actualmente por RSA.
En posteriores posts continuaré con este pequeño repaso a los métodos de factorización más conocidos.
Quizás también te interese:
.png)
.png)
.png)
Comentarios
Publicar un comentario