Algoritmo de Euclides estendido

En aritmética e programación informática, o algoritmo de Euclides estendido é unha extensión do algoritmo de Euclides que calcula, alén do máximo común divisor (mcd) dos números enteiros a e b, tamén os coeficientes da identidade de Bézout, que son números enteiros x e y tal que

 . 
E sendo   e  positivos, un de  ou  é negativo.

O algoritmo de Euclides estendido é particularmente útil cando a e b son coprimos. Con esa condición temos que x é o inverso multiplicativo modular de a módulo b, e y é o inverso multiplicativo modular de b módulo a. 

Do mesmo xeito, o algoritmo de Euclides polinómico estendido permite calcular o inverso multiplicativo en extensións de corpos alxébricos e, en particular, en corpos finitos de orde non prima. 

Cun algoritmo moi similar podemos calcular o máximo común divisor polinómico e os coeficientes da identidade de Bézout de dous polinomios dunha variable.

 Descrición 
O algoritmo de Euclides estándar son unha sucesión de divisións  cuxos cocientes non se utilizan. Só se usan os restos. Para o algoritmo estendido tamén fan falta os sucesivos cocientes. 



O algoritmo de Euclides estendido procede de xeito similar, mais engade outras dúas secuencias , sendo  os cocientes e  os restos como segue:

O cálculo tamén se detén cando  e dá

  é o máximo común divisor da entrada  e 
 Os coeficientes de Bézout son  e  é dicir 
 Os cocientes de a e b polo seu máximo común divisor veñen dados por  e 

A maiores, se a e b son ambos os dous positivos e , daquela



para  onde  denota a parte enteira de , é dicir, o maior enteiro non maior que .

Isto implica que o par de coeficientes de Bézout proporcionado polo algoritmo de Euclides estendido é o par mínimo de coeficientes de Bézout, xa que é o único par que satisfai ambas as desigualdades anteriores.

A continuación un exemplo pode clarificar.

 Exemplo 
A seguinte táboa mostra como funciona o algoritmo de Euclides estendido coas entradas  e . O máximo común divisor é a última entrada distinta de cero,    na columna "resto". O cálculo detense na fila 6, porque o resto é . Os coeficientes de Bézout aparecen nas dúas últimas entradas da penúltima fila. De feito, é doado verificar que    +    = 2. Finalmente, as dúas últimas entradas  e  da última fila son, ata o signo, os cocientes da entrada  e  polo máximo común divisor  .
índice i cociente c Resto r  s t 0    0 1      1 2  ÷  =  −  ×  =  −  ×  =  0 −  × 1 = −5 3  ÷  =  −  ×  =  −  ×  =  1 −  × −5 = 21 4  ÷  =  −  ×  =  −  ×  =  −5 −  × 21 = −26 5  ÷  =  −  ×  =  −  ×  =  21 −  × −26 =  6  ÷  =  −  ×  =  −  ×  =  −26 −  × 47 = 

A maiores, os cocientes, en azul, son os coeficientes da fracción continua de  = [5, 4, 1, 1, 2].

 Algoritmo polinómico de Euclides estendido 
Para polinomios dunha variable con coeficientes nun corpo, todo funciona de xeito similar, división euclidiana, identidade de Bézout e algoritmo de Euclides estendido. A primeira diferenza é que, na división de Euclides e no algoritmo, a desigualdade  ten que ser substituída por unha desigualdade nos graos do polinomio  Para o demais, todo o que precede neste artigo segue sendo o mesmo, simplemente substituíndo os enteiros por polinomios.

Unha segunda diferenza reside no límite do tamaño dos coeficientes de Bézout proporcionados polo algoritmo, que é máis preciso no caso polinómico, o que leva ao seguinte teorema.

En matemáticas, é común esixir que o máximo común divisor sexa un polinomio mónico. Para conseguir isto, abonda con dividir cada elemento da saída polo coeficiente principal de  Isto permite que, se a e b son coprimos, se obtén 1 no lado dereito da desigualdade de Bézout. En caso contrario, pódese obter calquera constante distinta de cero.

Se a e b son dous polinomios distintos de cero, entón o algoritmo de Euclides estendido produce o único par de polinomios (s, t) tal que



O algoritmo de Euclides estendido é a ferramenta esencial para calcular inversos multiplicativos en estruturas modulares, normalmente os enteiros modulares e as extensións de corpos alxébricos. Un exemplo notable deste último caso son os corpos finitos de orde non prima.



Unha terceira diferenza é que, no caso polinómico, o máximo común divisor defínese só ata a multiplicación por unha constante distinta de cero. Hai varias formas de definir sen ambigüidades un máximo común divisor.



 Cálculo de inversos multiplicativos en aritmética modular 

 Números enteiros modulares 
Un elemento  do anel   ten un inverso multiplicativo (é dicir, é unha unidade) se é coprimo con . En particular, se  é primo,  ten un inverso multiplicativo se non é cero (módulo ). Así,  é un corpo se e só se  é primo.

A identidade de Bézout afirma que  e  son primos primos se e só se existen números enteiros  e  tal que



Reducindo esta identidade módulo  dáse



Así , ou, máis exactamente, o resto da división de  por , é o inverso multiplicativo de  módulo .

 Extensións simples de corpos alxébricos 

 Exemplo 
Por exemplo, se o polinomio usado para definir o corpo finito GF(28) é , e  é o elemento cuxo inverso se desexa, entón a realización do algoritmo dá como resultado o cálculo descrito na seguinte táboa embaixo. Lembremos que en corpos de orde 2n, un ten − z = z e z + z = 0 para cada elemento z do corpo). Temos que 1 é o único elemento distinto de cero en GF(2).
paso cociente r s t  1 0  0 1 1   1  2     3     4   
Así, o inverso é , como se pode confirmar multiplicando os dous elementos xuntos e tomando o resto por  do resultado.

 O caso de máis de dous números 
Pódese manexar o caso de máis de dous números de forma iterativa. 



 Notas 

 Véxase tamén 

 Bibliografía 
  Volume 2, Chapter 4.
 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. . Pages 859–861 of section 31.2: Greatest common divisor.

 Outros artigos 
 Dominio euclidiano
 Teorema chinés do resto
 Inverso multiplicativo modular

 Ligazóns externas 

 Source for the form of the algorithm used to determine the multiplicative inverse in GF(2^8)

Categoría:Teoría de números