Algoritmo extendido de euclides: encuentra el inverso modular y el mcd

★★★★★Valoración: 4.87 (604 votos)

En el ámbito de la teoría de números, el algoritmo extendido de Euclides es una herramienta fundamental que nos permite calcular tanto el máximo común divisor (MCD) de dos enteros como su inverso modular. Este algoritmo, una extensión del algoritmo de Euclides clásico, es esencial en criptografía, teoría de la información y otras áreas que involucran operaciones con números enteros.

Tabla de Contenido

Algoritmo de Euclides Clásico

Antes de adentrarnos en el algoritmo extendido, repasemos brevemente el algoritmo de Euclides clásico. Este algoritmo se basa en el principio de que el MCD de dos enteros ay b(donde a> b) es el mismo que el MCD de by el resto de la división de aentre b.

En términos matemáticos:

MCD( a, b) = MCD( b, amod b)

El algoritmo se repite hasta que el resto de la división sea 0. El último divisor no nulo es el MCD de ay b.

Ejemplo

Calcula el MCD de 24 y 18:

  1. 24 mod 18 = 6
  2. 18 mod 6 = 0

Por lo tanto, MCD(24, 18) =

Algoritmo Extendido de Euclides

El algoritmo extendido de Euclides va un paso más allá, no solo calculando el MCD, sino también encontrando los coeficientes sy tque satisfacen la siguiente ecuación:

a s+ b t= MCD( a, b)

El algoritmo funciona realizando una secuencia de operaciones similares al algoritmo de Euclides clásico, pero manteniendo un seguimiento de los coeficientes sy ten cada paso.

Pasos del Algoritmo

  1. Inicialización:
    • s 0 = 1
    • t 0 = 0
    • s 1 = 0
    • t 1 = 1
    • r 0 = a
    • r 1 = b
  2. Iteración:
    • Para i = 1, 2, 3, ... hasta que r i = 0:
      • q i = r i -2 // r i -1 (cociente de la división)
      • r i = r i -2 - q i r i -1 (resto de la división)
      • s i = s i -2 - q i s i -1
      • t i = t i -2 - q i t i -1
  3. Resultado:
    • MCD( a , b ) = r i -1
    • s = s i -1
    • t = t i -1

Ejemplo

Calcula el MCD(24, 18) y los coeficientes sy t:

i r i q i s i t i
0 24 1 0
1 18 0 1
2 6 1 1 -1
3 0 3 -3 4

El algoritmo termina en i= 3, ya que r 3= 0. Por lo tanto:

  • MCD(24, 18) = r 2 = 6
  • s = s 2 = 1
  • t = t 2 = -1

Verificando la ecuación original: 24 1 + 18 (-1) =

Inverso Modular

El algoritmo extendido de Euclides también se puede utilizar para calcular el inverso modular de un entero amódulo m, denotado como a -1mod m. El inverso modular de aes un entero btal que:

a b≡ 1 (mod m)

Si el MCD( a, m) = 1, entonces el inverso modular de aexiste y se puede calcular usando el algoritmo extendido de Euclides.

Pasos para Calcular el Inverso Modular

  1. Utilizar el algoritmo extendido de Euclides para encontrar los coeficientes s y t tales que:

    2. a s + m t = MCD( a , m ) = 1

  2. El inverso modular de a módulo m es:

    3. a -1 mod m ≡ s mod m

    calculo de inverso con algoritmo extendido de euclides - Cómo calcular el MCD con el algoritmo de Euclides

    Ejemplo

    Calcula el inverso modular de 7 módulo 11:

    1. Utilizando el algoritmo extendido de Euclides, encontramos que s = 3 y t = -
    2. Por lo tanto, 7 -1 mod 11 ≡ 3 mod 1

    Aplicaciones del Algoritmo Extendido de Euclides

    El algoritmo extendido de Euclides tiene diversas aplicaciones en áreas como:

    • Criptografía:
      • Cifrado RSA
      • Intercambio de claves Diffie-Hellman
    • Teoría de la Información:
      • Códigos de corrección de errores
    • Matemáticas:
      • Resolución de ecuaciones diofánticas
      • Cálculo de fracciones continuas

    Conclusión

    El algoritmo extendido de Euclides es una herramienta poderosa que nos permite calcular el máximo común divisor ( MCD ) y el inverso modular de dos enteros. Este algoritmo tiene amplias aplicaciones en áreas como criptografía , teoría de la información y otras disciplinas que involucran operaciones con números enteros.

Si quieres conocer otros artículos parecidos a Algoritmo extendido de euclides: encuentra el inverso modular y el mcd puedes visitar la categoría Finanzas / Inversiones.

Subir