Algoritmo euclidiano extendido

En aritmética y programación informática , el algoritmo euclidiano extendido es una extensión del algoritmo euclidiano y calcula, además del máximo común divisor (mcd) de los enteros a y b , también los coeficientes de la identidad de Bézout , que son enteros x e y tales que${\displaystyle ax+by=\gcd(a,b)}$; generalmente se denota como${\displaystyle \operatorname {xgcd} (a,b)}$.

Este es un algoritmo certificador , porque el mcd es el único número que puede satisfacer simultáneamente esta ecuación y dividir las entradas. ^{[ 1 ]} Permite calcular también, casi sin costo adicional, los cocientes de a y b por su máximo común divisor.

El algoritmo euclidiano extendido también hace referencia a un algoritmo muy similar para calcular el máximo común divisor de un polinomio y los coeficientes de la identidad de Bézout de dos polinomios univariados .

El algoritmo euclidiano extendido resulta especialmente útil cuando a y b son coprimos . En este caso, x es el inverso multiplicativo modular de a módulo b , e y es el inverso multiplicativo modular de b módulo a . De forma similar, el algoritmo euclidiano extendido polinomial permite calcular el inverso multiplicativo en extensiones de cuerpos algebraicos y, en particular, en cuerpos finitos de orden no primo. Por consiguiente, ambos algoritmos euclidianos extendidos se utilizan ampliamente en criptografía . En concreto, el cálculo del inverso multiplicativo modular es un paso esencial en la derivación de pares de claves en el método de cifrado de clave pública RSA .

El algoritmo euclidiano estándar procede mediante una sucesión de divisiones euclidianas cuyos cocientes no se utilizan. Solo se conservan los restos . Para el algoritmo extendido, se utilizan los cocientes sucesivos. Más precisamente, el algoritmo euclidiano estándar con a y b como entrada, consiste en calcular una secuencia${\displaystyle q_{1},\ldots ,q_{k}}$de cocientes y una secuencia${\displaystyle r_{0},\ldots ,r_{k+1}}$de restos tales que

${\displaystyle {\begin{aligned}r_{0}&=a\\r_{1}&=b\\&\,\,\,\vdots \\r_{i+1}&=r_{i-1}-q_{i}r_{i}\quad {\text{y}}\quad 0\leq r_{i+1}<|r_{i}|\quad {\text{(esto define }}q_{i})\\&\,\,\,\vdots \end{aligned}}}$

La principal propiedad de la división euclidiana es que las desigualdades de la derecha definen de forma única${\displaystyle q_{i}}$y${\displaystyle r_{i+1}}$de${\displaystyle r_{i-1}}$y${\displaystyle r_{i}.}$

El cálculo se detiene cuando se alcanza un resto.${\displaystyle r_{k+1}}$que es cero; el máximo común divisor es entonces el último resto distinto de cero.${\displaystyle r_{k}.}$

El algoritmo euclidiano extendido procede de manera similar, pero agrega otras dos secuencias, como sigue:

${\displaystyle {\begin{aligned}r_{0}&=a&r_{1}&=b\\s_{0}&=1&s_{1}&=0\\t_{0}&=0&t_{1}&=1\\&\,\,\,\vdots &&\,\,\,\vdots \\r_{i+1}&=r_{i-1}-q_{i}r_{i}&{\text{y }}0&\leq r_{i+1}<|r_{i}|&{\text{(esto define }}q_{i}{\text{)}}\\s_{i+1}&=s_{i-1}-q_{i}s_{i}\\t_{i+1}&=t_{i-1}-q_{i}t_{i}\\&\,\,\,\vdots \end{aligned}}}$

El cálculo también se detiene cuando${\displaystyle r_{k+1}=0}$y da

• ${\displaystyle r_{k}}$es el máximo común divisor de la entrada${\displaystyle a=r_{0}}$y${\displaystyle b=r_{1}.}$
• Los coeficientes de Bézout son${\displaystyle s_{k}}$y${\displaystyle t_{k},}$eso es${\displaystyle \gcd(a,b)=r_{k}=as_{k}+bt_{k}}$
• Los cocientes de a y b por su máximo común divisor vienen dados por${\displaystyle s_{k+1}=\pm {\frac {b}{\gcd(a,b)}}}$y${\displaystyle t_{k+1}=\mp {\frac {a}{\gcd(a,b)}}}$(el letrero${\displaystyle \mp }$es opuesto a${\displaystyle \pm }$).

Además, si a y b son ambos positivos y${\displaystyle \gcd(a,b)\neq \min(a,b)}$, entonces

${\displaystyle |s_{i}|\leq \left\lfloor {\frac {b}{2\gcd(a,b)}}\right\rfloor \quad {\text{y}}\quad |t_{i}|\leq \left\lfloor {\frac {a}{2\gcd(a,b)}}\right\rfloor }$

para${\displaystyle 0\leq i\leq k,}$dónde${\displaystyle \lfloor x\rfloor }$denota la parte entera de x , es decir, el mayor entero que no es mayor que x .

Esto implica que el par de coeficientes de Bézout proporcionado por el algoritmo euclidiano extendido es el par mínimo de coeficientes de Bézout, al ser el único par que satisface ambas desigualdades anteriores.

También significa que si a y b se ajustan a un tipo de datos entero sin signo , un programa informático puede calcular los coeficientes de Bézout en el tipo entero con signo correspondiente sin desbordamiento de enteros .

Ejemplos

La siguiente tabla muestra cómo procede el algoritmo euclidiano extendido con las entradas 240 y 46. El máximo común divisor es la última entrada no nula, 2, en la columna "resto". El cálculo se detiene en la fila 6, porque el resto en ella es 0. Los coeficientes de Bézout aparecen en las dos últimas columnas de la penúltima fila. De hecho, es fácil verificar que −9 × 240 + 47 × 46 = 2. Finalmente, las dos últimas entradas 23 y −120 de la última fila son, salvo el signo, los cocientes de las entradas 46 y 240 por el máximo común divisor 2 .

El siguiente ejemplo utiliza una notación más compacta. El máximo común divisor de${\displaystyle a=68}$y${\displaystyle b=30}$se puede calcular de esta manera:

${\displaystyle g=\mathrm {gcd} {\underset {\color {Green}\scriptstyle \;\;^{\uparrow }\!\!-\!-\!(-2)}{(68,30)}}=\mathrm {gcd} {\underset {\color {Green}\scriptstyle \!(-3)\!-\!\!-\!^{\uparrow }\;\;}{(8,30)}}}$${\displaystyle =\mathrm {gcd} {\underset {\color {Green}\scriptstyle \;^{\uparrow }\!\!-\!\!-\!(-1)\!\!}{(8,\,6)}}=\mathrm {gcd} {\underset {\color {Green}\scriptstyle \!\!(-3)\!-\!\!-\!^{\uparrow }\;}{(2,\,6)}}=\mathrm {gcd} (2,0)=2,}$

dónde${\displaystyle \color {Green}\scriptstyle \,^{\uparrow }\!\!-\!-\!(-2)}$en el primer paso significa que${\displaystyle -2}$veces${\displaystyle 30}$se agrega a${\displaystyle 68}$(el mcd no cambia al sumar un múltiplo de un número a otro).

Aplicando las sumas de múltiplos indicadas en verde de forma análoga a las ecuaciones, comenzando con${\displaystyle a=1a+0b}$y${\displaystyle b=0a+1b,}$conduce a${\displaystyle g=4a-9b,}$Según los cálculos adyacentes (la tabla correspondiente del extremo derecho utiliza operaciones de fila).

Para polinomios univariados con coeficientes en un cuerpo , todo funciona de manera similar: división euclidiana, identidad de Bézout y algoritmo euclidiano extendido. La primera diferencia es que, en la división euclidiana y el algoritmo, la desigualdad${\displaystyle 0\leq r_{i+1}<|r_{i}|}$debe ser reemplazado por una desigualdad en los grados${\displaystyle \deg r_{i+1}<\deg r_{i}.}$Por lo demás, todo lo anterior en este artículo permanece igual, simplemente sustituyendo los números enteros por polinomios.

Una segunda diferencia radica en la cota del tamaño de los coeficientes de Bézout proporcionada por el algoritmo euclidiano extendido, que es más preciso en el caso polinomial, lo que lleva al siguiente teorema.

Si a y b son dos polinomios distintos de cero, entonces el algoritmo euclidiano extendido produce el par único de polinomios ( s , t ) tal que

${\displaystyle as+bt=\gcd(a,b)}$

y

${\displaystyle \deg s<\deg b-\deg(\gcd(a,b)),\quad \deg t<\deg a-\deg(\gcd(a,b)).}$

Una tercera diferencia radica en que, en el caso polinómico, el máximo común divisor se define únicamente hasta la multiplicación por una constante distinta de cero. Existen varias maneras de definir de forma inequívoca un máximo común divisor.

En matemáticas, es común requerir que el máximo común divisor sea un polinomio mónico . Para obtener esto, basta con dividir cada elemento de la salida por el coeficiente principal de${\displaystyle r_{k}.}$Esto permite que, si a y b son coprimos, se obtenga 1 en el lado derecho de la desigualdad de Bézout. De lo contrario, se puede obtener cualquier constante distinta de cero. En álgebra computacional , los polinomios suelen tener coeficientes enteros, y esta forma de normalizar el máximo común divisor introduce demasiadas fracciones para resultar práctica.

La segunda forma de normalizar el máximo común divisor en el caso de polinomios con coeficientes enteros es dividir cada salida por el contenido de${\displaystyle r_{k},}$para obtener un máximo común divisor primitivo . Si los polinomios de entrada son coprimos, esta normalización también proporciona un máximo común divisor igual a 1. La desventaja de este método es que se deben calcular y simplificar muchas fracciones durante el proceso.

Un tercer enfoque consiste en extender el algoritmo de secuencias de pseudorestos subresultantes de una manera similar a la extensión del algoritmo euclidiano al algoritmo euclidiano extendido. Esto permite que, al comenzar con polinomios con coeficientes enteros, todos los polinomios que se calculan tengan coeficientes enteros. Además, cada resto calculado${\displaystyle r_{i}}$es un polinomio subresultante . En particular, si los polinomios de entrada son coprimos, entonces la identidad de Bézout se convierte en

${\displaystyle as+bt=\operatorname {Res} (a,b),}$

dónde${\displaystyle \operatorname {Res} (a,b)}$denota la resultante de a y b . En esta forma de la identidad de Bézout, la fórmula no tiene denominador. Si se divide todo por la resultante, se obtiene la identidad de Bézout clásica, con un denominador común explícito para los números racionales que aparecen en ella.

Para implementar el algoritmo descrito anteriormente, cabe destacar que en cada paso solo se necesitan los dos últimos valores de las variables indexadas. Por lo tanto, para ahorrar memoria, cada variable indexada debe reemplazarse por tan solo dos variables.

Para simplificar, el siguiente algoritmo (y los demás algoritmos de este artículo) utiliza asignaciones paralelas . En un lenguaje de programación que no tenga esta característica, las asignaciones paralelas deben simularse con una variable auxiliar. Por ejemplo, la primera,

(old_r, r) := (r, old_r - cociente × r)

es equivalente a

prov := r; r := old_r - cociente × prov; old_r := prov;

y de forma similar para las demás asignaciones paralelas. Esto da como resultado el siguiente código:

función extended_gcd(a, b) (old_r, r) := (a, b) (old_s, s) := (1, 0) (old_t, t) := (0, 1) mientras r ≠ 0 hacer cociente := old_r div r (old_r, r) := (r, old_r − cociente × r) (old_s, s) := (s, old_s − cociente × s) (old_t, t) := (t, old_t − cociente × t) Salida "Coeficientes de Bézout:", (old_s, old_t) Salida "Máximo común divisor:", old_r Salida "Cocientes por el mcd:", (t, s)

Los cocientes de a y b por su máximo común divisor, que se muestran en la salida, pueden tener un signo incorrecto. Esto se corrige fácilmente al final del cálculo, pero no se ha hecho aquí para simplificar el código. Del mismo modo, si a o b es cero y el otro es negativo, el máximo común divisor que se muestra es negativo y se deben cambiar todos los signos de la salida.

Finalmente, observe que en la identidad de Bézout,${\displaystyle ax+by=\gcd(a,b)}$, uno puede resolverlo${\displaystyle y}$dado${\displaystyle a,b,x,\gcd(a,b)}$. Por lo tanto, una optimización del algoritmo anterior consiste en calcular solo el${\displaystyle s_{k}}$secuencia (que produce el coeficiente de Bézout)${\displaystyle x}$), y luego calcular${\displaystyle y}$al final:

función extended_gcd(a, b) s := 0; old_s := 1 r := b; old_r := a mientras r ≠ 0 hacer cociente := old_r div r (old_r, r) := (r, old_r − cociente × r) (old_s, s) := (s, old_s − cociente × s) Si b ≠ 0, entonces bezout_t := (old_r − old_s × a) div b; de lo contrario bezout_t := 0 Salida "Coeficientes de Bézout:", (old_s, bezout_t) Salida "Máximo común divisor:", old_r

Sin embargo, en muchos casos esto no es realmente una optimización: mientras que el algoritmo anterior no es susceptible al desbordamiento cuando se usa con enteros de máquina (es decir, enteros con un límite superior fijo de dígitos), la multiplicación de old_s × a en el cálculo de bezout_t puede desbordarse, lo que limita esta optimización a entradas que se pueden representar en menos de la mitad del tamaño máximo. Cuando se usan enteros de tamaño ilimitado, el tiempo necesario para la multiplicación y la división crece cuadráticamente con el tamaño de los enteros. Esto implica que la "optimización" reemplaza una secuencia de multiplicaciones/divisiones de enteros pequeños por una sola multiplicación/división, que requiere más tiempo de cálculo que las operaciones que reemplaza, tomadas en conjunto.

Una fracción ⁠ a / b ⁠ está en forma simplificada canónica si a y b son coprimos y b es positivo. Esta forma simplificada canónica se puede obtener reemplazando las tres líneas de salida del pseudocódigo anterior por

Si s = 0, entonces imprime "División por cero". Si s < 0, entonces s := − s ; t := − t ( para evitar denominadores negativos ). Si s = 1 , entonces imprime − t ( para evitar denominadores iguales a 1). Imprime ⁠ − t / s ⁠.

La demostración de este algoritmo se basa en el hecho de que s y t son dos enteros coprimos tales que cuando + bt = 0 , y por lo tanto${\displaystyle {\frac {a}{b}}=-{\frac {t}{s}}}$Para obtener la forma simplificada canónica, basta con mover el signo menos para tener un denominador positivo.

Si b divide a de forma exacta, el algoritmo ejecuta solo una iteración y obtenemos s = 1 al final del algoritmo. Este es el único caso en el que el resultado es un número entero.

El algoritmo euclidiano extendido es la herramienta esencial para calcular inversos multiplicativos en estructuras modulares, típicamente los enteros modulares y las extensiones de cuerpos algebraicos . Un ejemplo notable de este último caso son los cuerpos finitos de orden no primo.

función inversa(a, n) t := 0; newt := 1 r := n; nuevor := a mientras que newr ≠ 0 hacer cociente := r div newr (t, newt) := (newt, t − cociente × newt) (r, nuevor) := (nuevor, r − cociente × nuevor) Si r > 1, entonces devuelve "a no es invertible". Si t < 0, entonces t := t + n devolver t

función inversa(a, p) t := 0; newt := 1 r := p; newr := a mientras que newr ≠ 0 hacer cociente := r div newr (r, nuevor) := (nuevor, r − cociente × nuevor) (t, newt) := (newt, t − cociente × newt) Si degree(r) > 0 , entonces devuelve "O bien p no es irreducible o bien a es un múltiplo de p". devolver (1/r) × t

Se puede abordar el caso de más de dos números de forma iterativa. Primero demostramos que${\displaystyle \gcd(a,b,c)=\gcd(\gcd(a,b),c)}$Para probar esto, dejemos${\displaystyle d=\gcd(a,b,c)}$Por definición de mcd${\displaystyle d}$es un divisor de${\displaystyle a}$y${\displaystyle b}$. De este modo${\displaystyle \gcd(a,b)=kd}$para algunos${\displaystyle k}$. Similarmente${\displaystyle d}$es un divisor de${\displaystyle c}$entonces${\displaystyle c=jd}$para algunos${\displaystyle j}$. Dejar${\displaystyle u=\gcd(k,j)}$. Mediante nuestra construcción de${\displaystyle u}$,${\displaystyle ud|a,b,c}$pero desde${\displaystyle d}$es el mayor divisor${\displaystyle u}$es una unidad . Y dado que${\displaystyle ud=\gcd(\gcd(a,b),c)}$El resultado está demostrado.

Entonces si${\displaystyle na+mb=\gcd(a,b)}$ entonces hay${\displaystyle x}$y${\displaystyle y}$de tal manera que${\displaystyle x\gcd(a,b)+yc=\gcd(a,b,c)}$por lo que la ecuación final será

${\displaystyle x(na+mb)+yc=(xn)a+(xm)b+yc=\gcd(a,b,c).\,}$

Entonces, para aplicarlo a n números, usamos la inducción.

${\displaystyle \gcd(a_{1},a_{2},\dots ,a_{n})=\gcd(a_{1},\,\gcd(a_{2},\,\gcd(a_{3},\dots ,\gcd(a_{n-1}\,,a_{n}))),\dots ),}$

con las ecuaciones que se derivan directamente.

• dominio euclidiano
• Teorema de congruencia lineal
• Kuṭṭaka

• Knuth, Donald . El arte de la programación informática . Addison-Wesley.Volumen 2, Capítulo 4.
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein . Introducción a los algoritmos , segunda edición. MIT Press y McGraw-Hill, 2001. ISBN 0-262-03293-7Páginas 859 – 861 de la sección 31.2: Máximo común divisor.

• Fuente de la forma del algoritmo utilizado para determinar el inverso multiplicativo en GF(2^8)