En aritmética y programación, el algoritmo euclídeo extendido es una generalización del algoritmo de Euclides, que además del máximo común divisor (mcd) de los enteros a y b, también calcula los coeficientes de la identidad de Bézout, que son los enteros x e y tales que ; generalmente se denota como .
Este es un algoritmo de certificación, porque el mcd es el único número que puede satisfacer simultáneamente esta ecuación y dividir los dos datos de entrada. Permite calcular también, casi sin coste de computación adicional, los cocientes de a y b por su máximo común divisor.
también hace referencia a un algoritmo muy similar para calcular el máximo común divisor polinómico y los coeficientes de la identidad de Bézout de dos polinomios.
El algoritmo euclídeo extendido es particularmente útil cuando a y b son números coprimos. En ese 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 manera similar, el algoritmo euclídeo extendido polinómico permite calcular el inverso multiplicativo en extensión algebraica y, en particular, en cuerpo finito de orden no primo. Por consiguiente, ambos algoritmos euclídeos extendidos se utilizan ampliamente en criptografía. En particular, 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.
Descripción El algoritmo euclídeo estándar procede mediante una sucesión de divisiones euclídeas cuyos cocientes no se utilizan. Solo se conservan los restos. En el algoritmo extendido, se utilizan cocientes sucesivos. Más precisamente, el algoritmo euclídeo estándar con a y b como entrada, consiste en calcular una secuencia de cocientes y una secuencia de restos, de modo que:
La propiedad principal de la división euclídea es que las desigualdades de la derecha definen de forma única y a partir de y
El cálculo se detiene cuando se alcanza un resto igual a cero. El máximo común divisor es entonces el último resto distinto de cero
El algoritmo euclídeo extendido procede de forma similar, pero añade otras dos secuencias, como sigue:
El cálculo también se detiene cuando y da como resultado:
es el máximo común divisor de las secuencias de entrada y Los coeficientes de Bézout son y , es decir, . Los cocientes de a y b por su máximo común divisor son y (el signo representa el opuesto de ).
Además, si a y b son ambos positivos y , entonces:
para , donde denota la parte entera de , es decir, el mayor entero no mayor que .
Esto implica que el par de coeficientes de Bézout proporcionados por el algoritmo euclídeo 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 caben en un tipo de dato entero sin signo, un programa informático puede calcular los coeficientes de Bézout en el tipo de entero con signo correspondiente sin desbordamiento.
Ejemplos
La siguiente tabla muestra cómo procede el algoritmo euclídeo 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, ya que 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 .
Índice i Cociente qi−1 Resto ri si ti024010146012240 ÷ 46= 5240 − 5 × 46= 101 − 5 × 0= 10 − 5 × 1= −5 346 ÷ 10= 446 − 4 × 10= 60 − 4 × 1= −41 − 4 × −5= 21410 ÷ 6= 110 − 1 × 6= 41 − 1 × −4= 5−5 − 1 × 21= −2656 ÷ 4= 16 - 1 × 4= 2-4 - 1 × 5= -921 - 1 × -26= 4764 ÷ 2= 24 - 2 × 2= 05 - 2 × -9= 23-26 - 2 × 47= -120
El siguiente ejemplo utiliza una notación más compacta. El máximo común divisor de y se puede calcular así:
donde en el primer paso significa que multiplicado por se suma a (el mcd no cambia al sumar un múltiplo de un número al otro).
Aplicando las sumas de múltiplos indicadas en verde de forma análoga a las ecuaciones, partiendo de y , se obtiene según los cálculos adyacentes (la tabla correspondiente de la derecha utiliza operaciones de fila).
Demostración Dado que , entonces es una sucesión estrictamente decreciente de enteros no negativos para . Por lo tanto, debe detenerse con algún . Esto demuestra que el algoritmo finalmente se detiene.
De la ecuación se deduce que . En consecuencia, . Hasta este punto, la demostración es la misma que la del algoritmo euclídeo clásico.
Las relaciones de recurrencia para ,
pueden demostrarse por inducción. De hecho, para se reducen a:
Suponiendo que se satisfacen para algún , las ecuaciones para se obtienen del cálculo:
En particular, la ecuación muestra que y son números coprimos.
Multiplicando por , se obtiene:
Por lo tanto, , de donde se deduce que divide a . En consecuencia, existe un entero tal que . Al dividir por , la relación da como resultado Por lo tanto, y son enteros coprimos que son los cocientes de y por un factor común, que es su máximo común divisor o su opuesto.
Para demostrar la última afirmación, supóngase que y son ambos positivos y . Entonces, , y si , se puede observar que las secuencias s y t para (a,b) bajo la algoritmo euclídeo extendido son, salvo ceros y unos iniciales, las secuencias t y s para (b,a). Las definiciones muestran entonces que el caso (a,b) se reduce al caso (b,a). Así pues, supóngase que = sin pérdida de generalidad.
Se observa que es 1 y (que existe por ) es un entero negativo. Posteriormente, los alternan de signo y aumentan estrictamente en magnitud, lo cual se deduce inductivamente de las definiciones y del hecho de que = , y el caso se cumple por . Lo mismo ocurre con los después de los primeros términos, por la misma razón. Además, es fácil ver que (cuando a y b son ambos positivos) = . Así, al observar que , se obtiene:
Esto, junto con el hecho de que es mayor o igual en valor absoluto que cualquier o anterior, respectivamente, completa la demostración.
Algoritmo euclídeo extendido polinómico
Para polinomios con coeficientes en un cuerpo, todo funciona de manera similar: división euclídea, identidad de Bézout y algoritmo euclídeo extendido. La primera diferencia radica en que, tanto en la división euclídea como en el algoritmo, la desigualdad debe reemplazarse por una desigualdad en los grados Por lo demás, todo lo anterior en este artículo permanece igual, simplemente reemplazando los enteros por polinomios.
Una segunda diferencia radica en la cota del tamaño de los coeficientes de Bézout proporcionada por el algoritmo euclídeo extendido, que es más preciso en el caso polinómico, lo que conduce al siguiente teorema:
Si a y b son dos polinomios distintos de cero, entonces el algoritmo euclídeo extendido produce el único par de polinomios (s, t) tales que:
y
Una tercera diferencia es que, en el caso polinómico, el máximo común divisor se define solo hasta la multiplicación por una constante distinta de cero. Existen varias maneras de definir unívocamente un máximo común divisor.
En matemáticas, es común exigir 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 de 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 cálculo simbólico, los polinomios suelen tener coeficientes enteros, y esta forma de normalizar el máximo común divisor introduce demasiadas fracciones para ser conveniente.
La segunda forma de normalizar el máximo común divisor en el caso de polinomios con coeficientes enteros consiste en dividir cada salida por el contenido de 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 cálculo.
Un tercer enfoque consiste en extender el algoritmo de la secuencia de pseudo-restos subresultantes de forma similar a la extensión del algoritmo euclídeo al algoritmo euclídeo extendido. Esto permite que, al partir de polinomios con coeficientes enteros, todos los polinomios calculados tengan coeficientes enteros. Además, cada resto calculado es un polinomio subresultante. En particular, si los polinomios de entrada son coprimos, la identidad de Bézout se convierte en:
donde denota el resultante de a y b. En esta forma de la identidad de Bézout, la fórmula carece de denominador. Al dividir todo por el 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.
Pseudocódigo NOTA: En esta sección y en las siguientes, div es una función auxiliar que calcula el cociente de la división euclídea de su argumento izquierdo por su argumento derecho.
Para implementar el algoritmo descrito anteriormente, cabe destacar que solo se necesitan los dos últimos valores de las variables indexadas en cada paso. Por lo tanto, para ahorrar memoria, cada variable indexada debe reemplazarse por solo dos variables.
Para simplificar, el siguiente algoritmo (y los demás algoritmos de este artículo) utilizan asignación paralela. En un lenguaje de programación que no disponga de 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 mcd_extendido(a, b) (old_r, r) := (a, b) (old_s, s) := (1, 0) (old_t, t) := (0, 1)
mientras r ≠ 0 hacer cociente := old_r dividir 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" 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 muestra 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. De manera similar, 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, , se puede resolver dado . Por lo tanto, una optimización del algoritmo anterior consiste en calcular únicamente la secuencia (que produce el coeficiente de Bézout ) y, finalmente, calcular :
función mcd_extendido(a, b) s := 0; old_s := 1 r := b; old_r := a
mientras r ≠ 0 hacer cociente := old_r dividir 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) dividir b si no bezout_t := 0
salida "Coeficientes de Bézout:", (old_s, bezout_t) salida "Máximo común divisor:", old_r