Búscalo aquí:

Problema de Factorización Entera: Algoritmo de Pollard Rho [código]

Uno de los problemas de la Teroría de Números y que es la base de la robustez de muchos algorimos de cifrado (como el RSA), es el problema de la factorización entera. El problema se establece en hallar la factorización de un entero n en factores primos.


La formulación del problema se puede resumir en simplemente en factorizar un número compuesto. Para resolver esto, hay diferentes algoritmos, los mismos que se clasifican entre algoritmos de propósito general y de propósito especial.

En este post se presenta el algoritmo de Pollar Rho, el cual es de propósito especial. El código fuente en Java del algoritmo de Pollard Rho es el siguiente:

  1. /*
  2. @author: Jorge Valverde
  3. */
  4. public static long pollardRho(long n)
  5. {
  6. long a = 2;
  7. long b = 2;
  8. long d = 1;
  9. boolean band = false;
  10. while(band==false)
  11. {
  12. a = ((a*a)+1)%n;
  13. b=((b*b)+1)%n;
  14. b=((b*b)+1)%n;
  15. d = mcd((a-b),n);
  16. if(d>1 && d<n )
  17. band = true;
  18. if(d>=n)
  19. {
  20. d = 1;
  21. band = true;
  22. }
  23. }
  24. return d;
  25. }

-->El código de la función mcd se encuentra en el siguiente post.

Así mismo, haciendo uso de esta función se puede determinar el código de la función generedor de primos. El código en Java de la función getGenerador, es el siguiente:

  1. /*
  2. @author: Jorge Valverde
  3. */
  4. private static long getGenerador(long n)
  5. {
  6. long p = pollardRho(n-1);
  7. long q = (long)(n-1)/p;
  8. boolean band=false;
  9. long g=2,a,b;
  10. while(g<=n-1 && band==false)
  11. {
  12. a = (long) (Math.pow(2,(n-1)/p))%n;
  13. b = (long) (Math.pow(2,(n-1)/q))%n;
  14. if(a!=1 && b!=1)
  15. band=true;
  16. else
  17. g++;
  18. }
  19. if(band==false)
  20. g=0;
  21. return g;
  22. }

-->Espero les sea de utilidad, saludos.



Quieres leer más post como éste???...suscribete aquí!!!


2 comentarios:

Bienvenido a jcGeorge's Blog!!!

Por favor deja tu comentario, consulta o sugerencia, procura mantener habilitado tu perfil de Blogger o deja un enlace a tu blog o web.

Gracias por leer este blog!!!

Related Posts Plugin for WordPress, Blogger...