Búscalo aquí:

Algoritmo de Euclides Extendido [código]

Para realizar muchas aplicaciones en computación, sobre todo en el área de matemática aplicada, como por ejemplo, en lo que respecta a algoritmos de cifrado, se necesita de manera imprescindible contar con un fundamento en Matemática Discreta. Debido a que algunos lectores despues de haber leído el post de cifrado de imágenes me han pedido ayuda acerca de los algoritmos básicos para realizar el cifrado de información. Es por eso que, publicaré el código de algunos algoritmos implementados en el curso de Algebra Universal para Ciencias de la Computación que posteriormente servirán para algoritmos de cifrado como el RSA, ElGamal, Goldwasser-Micali, entre otros.

El primer algoritmo a presentar es el de Euclides Extendido, para calcular el máximo común divisor de dos números, tarea que puede parecer sencilla, pero cuya importancia es básica. El algoritmo de Euclides fue presentado por Euclides en su obra Elementos, y el algoritmo de Euclides Extendido es una modificación de éste, que permite expresar el máximo común divisor como una combinación lineal.

Se debe tener en cuenta que, apuntando a aplicaciones de cifrado (encriptación) de información, el manejo de ésta será mediante el uso de números enteros (Teoría de Números) de gran longitud (números grandes para dificultar el descifrado por parte de los intrusos), por lo tanto, la implementación debe ser eficiente.

Se recomienda la creación de un paquete especial para almacenar el código de las funciones que utilizaremos. A continuación, el código en Java de la función para calcular el máximo común divisor usando el algoritmo de Euclides (simple).

  1. //mcd usando el euclides simple
  2. public static long mcd(long a, long b)
  3. {
  4. long r;
  5. while(b!=0)
  6. {
  7. r = a%b;
  8. a = b;
  9. b = r;
  10. }
  11. return a;
  12. }

-->A contiuación, el código en Java que implementa la función Euclides Extendido:

  1. /* procedimiento que calcula el valor del maximo común divisor
  2. * de a y b siguiendo el algoritmo de euclides extendido,
  3. * devolviendo en un arreglo la siguiente estructura [d,x,y]
  4. * donde:
  5. * mcd(a,b) = d = a*x + b*y
  6. **/
  7. public static long[] euclidesExtendido(long a, long b)
  8. {
  9. long[] resp = new long[3];
  10. long x=0,y=0,d=0;
  11. if(b==0)
  12. {
  13. resp[0] = a; resp[1] = 1; resp[2] = 0;
  14. }
  15. else
  16. {
  17. long x2 = 1, x1 = 0, y2 = 0, y1 = 1;
  18. long q = 0, r = 0;
  19. while(b>0)
  20. {
  21. q = (a/b);
  22. r = a - q*b;
  23. x = x2-q*x1;
  24. y = y2 - q*y1;
  25. a = b;
  26. b = r;
  27. x2 = x1;
  28. x1 = x;
  29. y2 = y1;
  30. y1 = y;
  31. }
  32. resp[0] = a;
  33. resp[1] = x2;
  34. resp[2] = y2;
  35. }
  36. return resp;
  37. }

Espero les sea de utilidad, saludos.



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




5 comentarios:

  1. Buena broder, justo lo que andaba buscando :D

    ResponderEliminar
  2. Te agradesco mucho,
    Esta bien detallado justo lo que necsitaba.

    gracias
    Atte, Pablo Cajas

    ResponderEliminar
  3. GRACIAS PARSE LO NESESITABA

    ResponderEliminar
  4. oye es muy bueno pero no logro entender lo del metodo es que no lo puedo correr si alguien me pudiera explicar lo agradesco de antemano

    ResponderEliminar

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...