Principio del Algoritmo:
El Algoritmo de Euclides Extendido no solo calcula el máximo común divisor mcd(a, m) de dos números enteros a y m, sino que también encuentra números enteros x e y tales que ax + my = gcd(a, m)。
Esta es una aplicación de la identidad de Bézout (ecuación de Bézout).
Pasos del Algoritmo:
- Algoritmo de Euclides:Calcula mcd(a, m) usando el algoritmo de división, registrando el cociente y el resto en cada paso.
- Sustitución hacia atrás:Partiendo del último paso, sustituye hacia atrás para expresar cada resto como una combinación lineal de a y m.
- Resolución de Coeficientes:Finalmente, obtén los coeficientes x e y que satisfacen ax + my = mcd(a, m).
Inverso Modular:
Cuando mcd(a, m) = 1 (es decir, a y m son coprimos), existe un inverso multiplicativo de a módulo m, denotado como a-1 mod m. En este caso, x es el inverso modular, que satisface a × x ≡ 1 (mod m)。
Si x es negativo, debe ajustarse a un valor positivo: x' = x mod m.
Aplicaciones:
- Criptografía:Calcular la clave privada en el algoritmo RSA requiere encontrar el inverso modular.
- Problemas de Teoría de Números:Resolver congruencias lineales de la forma ax ≡ b (mod m).
- Combinatoria:Cálculo de combinatoria modular (Teorema de Lucas, etc.)
- Programación Competitiva:Cálculo rápido de inverso modular para evitar problemas de precisión por división
Complejidad Temporal:
O(log min(a, m)), igual que el Algoritmo de Euclides
Identidad de Bézout:
Para cualquier par de números enteros a y m, existen números enteros x e y tales que ax + my = mcd(a, m). Estos coeficientes x e y se pueden calcular eficientemente usando el Algoritmo de Euclides Extendido.