Extended Euclidean Algorithm
El algoritmo euclidiano extendido calcula gcd(a,b) y además halla los coeficientes de Bézout x, y que satisfacen ax+by=gcd(a,b).
Propósito
Calcular inversos modulares y resolver ecuaciones diofánticas lineales; una herramienta fundamental de teoría de números y criptografía.
Mecanismo
Mantiene los coeficientes mientras retrocede por el algoritmo de Euclides: gcd(a,b)=gcd(b, a mod b), y al sustituir hacia atrás x=y_prev, y=x_prev-floor(a/b)*y_prev. Coste O(log min(a,b)).
Casos de uso
- Cálculo de inversos modulares
- Generación de claves RSA
- Ecuaciones diofánticas lineales