El algoritmo extendido de Euclides no solo calcula el máximo común divisor: encuentra coeficientes que lo expresan como combinación lineal de los números originales. Con ellos se obtienen inversos modulares y soluciones de ecuaciones lineales.
El algoritmo de Euclides calcula mcd(a, b) usando restos sucesivos. El algoritmo extendido conserva información adicional durante esas mismas divisiones: cómo escribir cada resto como una combinación de a y b.
El resultado conecta divisibilidad y álgebra. Es la herramienta estándar para encontrar inversos módulo m, resolver congruencias lineales y preparar operaciones utilizadas por algoritmos criptográficos.
Una combinación lineal de dos enteros a y b es cualquier número de la forma ax + by, donde x e y son enteros. Los coeficientes pueden ser positivos, negativos o cero.
El algoritmo extendido encontrará en particular una combinación lineal igual al máximo común divisor. No suele ser única: distintos pares de coeficientes pueden producir el mismo valor.
La identidad de Bézout afirma que, para enteros a y b no ambos nulos, existen enteros x e y tales que:
Esta identidad es más fuerte que conocer el mcd. Proporciona una ecuación concreta que relaciona los números originales y abre la puerta a calcular inversos cuando el mcd vale 1.
Partimos del mismo ejemplo del tema anterior:
El algoritmo extendido trabaja sobre estas igualdades, pero en vez de detenerse al encontrar 21, sustituye hacia atrás para expresar 21 en función de 252 y 105.
De la segunda división obtenemos 21 = 105 - 2·42. La primera división dice que 42 = 252 - 2·105. Sustituimos esa expresión:
Hemos encontrado coeficientes de Bézout: x = -2 e y = 5. Una comprobación directa da -2·252 + 5·105 = -504 + 525 = 21.
La sustitución hacia atrás funciona, pero puede resultar incómoda en cálculos largos. El método extendido mantiene para cada resto r una expresión r = ax + by desde el comienzo.
Así, junto a cada resto se actualizan dos coeficientes. Cuando aparece el último resto no nulo, sus coeficientes resuelven la identidad de Bézout.
Para 252 y 105, la tabla registra que cada resto es igual a 252x + 105y.
| Resto r | Coeficiente x de 252 | Coeficiente y de 105 |
|---|---|---|
| 252 | 1 | 0 |
| 105 | 0 | 1 |
| 42 | 1 | -2 |
| 21 | -2 | 5 |
| 0 | 5 | -12 |
La fila del resto 21 contiene el resultado útil: 21 = -2·252 + 5·105. La fila final se muestra solo para completar el proceso; el mcd es el último resto distinto de cero.
Supongamos que ranterior = ax1 + by1 y ractual = ax2 + by2. Si el siguiente resto es rnuevo = ranterior - q·ractual, entonces:
La regla elimina la necesidad de reconstruir sustituciones al finalizar. Esta es la forma más práctica de implementar el algoritmo.
function euclidesExtendido(a, b) {
if (!Number.isSafeInteger(a) || !Number.isSafeInteger(b) || (a === 0 && b === 0)) {
throw new Error("se requieren enteros seguros, no ambos cero");
}
const signoA = a < 0 ? -1 : 1;
const signoB = b < 0 ? -1 : 1;
let anteriorR = Math.abs(a), r = Math.abs(b);
let anteriorX = signoA, x = 0;
let anteriorY = 0, y = signoB;
while (r !== 0) {
const cociente = Math.floor(anteriorR / r);
[anteriorR, r] = [r, anteriorR - cociente * r];
[anteriorX, x] = [x, anteriorX - cociente * x];
[anteriorY, y] = [y, anteriorY - cociente * y];
}
return { mcd: anteriorR, x: anteriorX, y: anteriorY };
}
console.log(euclidesExtendido(252, 105));
// { mcd: 21, x: -2, y: 5 }La función devuelve un objeto con el mcd y los coeficientes de Bézout. La normalización de signos hace que el mcd sea siempre no negativo, incluso con entradas negativas.
Una buena práctica es comprobar la identidad que devuelve el algoritmo. Para el ejemplo, los coeficientes deben satisfacer exactamente ax + by = mcd.
const resultado = euclidesExtendido(252, 105);
const comprobacion = 252 * resultado.x + 105 * resultado.y;
console.log(resultado.mcd); // 21
console.log(comprobacion); // 21Esta comprobación es especialmente útil al implementar algoritmos numéricos, donde una variable actualizada en el orden equivocado puede producir coeficientes erróneos aunque el mcd parezca correcto.
Si a y m son coprimos, la identidad de Bézout toma la forma ax + my = 1. Al mirar la igualdad módulo m, el término my deja resto 0 y queda:
Esta es la conexión fundamental: el algoritmo extendido encuentra un inverso modular sin probar todos los residuos posibles.
Busquemos el inverso de 17 módulo 43. El algoritmo produce la identidad:
Los dos representantes son equivalentes porque -5 ≡ 38 (mod 43). En programación normalmente se normaliza el resultado a un valor entre 0 y m - 1.
function modulo(a, m) {
return ((a % m) + m) % m;
}
function inversoModular(a, m) {
if (!Number.isSafeInteger(m) || m <= 1) {
throw new Error("el módulo debe ser un entero mayor que 1");
}
const { mcd, x } = euclidesExtendido(a, m);
if (mcd !== 1) return null;
return modulo(x, m);
}
console.log(inversoModular(17, 43)); // 38
console.log(inversoModular(2, 8)); // nullEl valor null comunica que no existe inverso. No debe reemplazarse por cero: cero nunca puede ser un inverso multiplicativo módulo m mayor que 1.
Dividir entre a módulo m significa multiplicar por su inverso. Por ejemplo, para resolver 17x ≡ 9 (mod 43), multiplicamos por el inverso 38 de 17.
La operación solo es válida porque mcd(17, 43) = 1. Si el coeficiente no es coprimo con el módulo, hay que analizar el problema de otra manera.
Consideremos la ecuación ax ≡ b (mod m) y sea d = mcd(a, m). La ecuación tiene solución si y solo si d divide a b.
Cuando d divide a b, se pueden dividir a, b y m por d. El coeficiente reducido queda coprimo con el módulo reducido, por lo que ya posee inverso.
Resolvamos 6x ≡ 8 (mod 14). Como mcd(6, 14) = 2 y 2 divide a 8, la ecuación tiene dos soluciones módulo 14.
Comprobación: 6·6 = 36 ≡ 8 y 6·13 = 78 ≡ 8 módulo 14. Las soluciones se separan por 7, que es el módulo reducido.
La identidad de Bézout también explica qué cantidades se pueden formar combinando bloques de tamaños a y b. Todos los múltiplos de mcd(a, b) pueden expresarse como ax + by con coeficientes enteros.
En problemas físicos los coeficientes suelen requerirse no negativos, lo que añade restricciones. Pero la condición del mcd proporciona el criterio algebraico básico de posibilidad.
Los sistemas criptográficos de clave pública usan operaciones modulares con números muy grandes. Encontrar inversos es una operación central al generar algunas claves y al realizar transformaciones algebraicas.
Los ejemplos de este tema son educativos. En software real se deben usar bibliotecas criptográficas auditadas, tipos de precisión adecuados y protocolos establecidos, nunca implementar un sistema seguro desde cero a partir de estas fórmulas.
El algoritmo extendido realiza la misma cantidad asintótica de pasos que el algoritmo de Euclides: O(log min(|a|, |b|)). Solo agrega unas pocas operaciones enteras para actualizar los coeficientes.
Con Number, los enteros son exactos solamente hasta Number.MAX_SAFE_INTEGER. Para valores mayores se debe reescribir el algoritmo con BigInt, usando 0n, 1n y operaciones exclusivamente entre valores de ese tipo.
Number para cálculos criptográficos o enteros fuera del rango seguro.BigInt.El algoritmo extendido de Euclides transforma las divisiones sucesivas en información constructiva: no solo sabemos cuál es el mcd, sino cómo obtenerlo y cómo usarlo. En el próximo tema aplicaremos estas herramientas al contexto de la criptografía modular.