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

$ax+by=\gcd (a,b)$.

E sendo Modelo:Mvar e Modelo:Mvar positivos, un de Modelo:Mvar ou Modelo:Mvar é 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.

$\begin{array}{cccc}{r}_0& =a& r_1& =b\\ s_0& =1& s_1& =0\\ t_0& =0& t_1& =1\\ & ⋮& & ⋮\\ r_{i+1}& =r_{i-1}-c_i{r}_i& \text{e }0& \le r_{i+1}<|r_i|& \text{(isto define }{c}_i\text{)}\\ s_{i+1}& =s_{i-1}-c_i{s}_i\\ t_{i+1}& =t_{i-1}-c_i{t}_i\\ & ⋮\end{array}$

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

O cálculo tamén se detén cando $r_{k+1}=0$ e dá

• $r_k$ é o máximo común divisor da entrada $a=r_0$ e $b=r_1.$
• Os coeficientes de Bézout son $s_k$ e $t_k,$ é dicir $\gcd (a,b)=r_k=a{s}_k+b{t}_k$
• Os cocientes de a e b polo seu máximo común divisor veñen dados por $s_{k+1}=\pm \frac{b}{\gcd (a,b)}$ e $t_{k+1}=\pm \frac{a}{\gcd (a,b)}$

A maiores, se a e b son ambos os dous positivos e $\gcd (a,b)\ne \min (a,b)$, daquela

$|s_i|\le \lfloor \frac{b}{2\gcd (a,b)}\rfloor \text{e}|t_i|\le \lfloor \frac{a}{2\gcd (a,b)}\rfloor$

para $0\le i\le k,$ onde $\lfloor x\rfloor$ denota a parte enteira de Modelo:Mvar, é dicir, o maior enteiro non maior que Modelo:Mvar.

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 Modelo:Color e Modelo:Color. O máximo común divisor é a última entrada distinta de cero, Modelo:Color na columna "resto". O cálculo detense na fila 6, porque o resto é Modelo:Color. Os coeficientes de Bézout aparecen nas dúas últimas entradas da penúltima fila. De feito, é doado verificar que Modelo:Color $\cdot$ Modelo:Color + Modelo:Color $\cdot$ Modelo:Color = 2. Finalmente, as dúas últimas entradas Modelo:Color e Modelo:Color da última fila son, ata o signo, os cocientes da entrada Modelo:Color e Modelo:Color polo máximo común divisor Modelo:Color.

índice i	cociente cModelo:Sub	Resto rModelo:Sub	sModelo:Sub	tModelo:Sub
0		Modelo:Color	Modelo:Color	0
1		Modelo:Color	Modelo:Color	1
2	Modelo:Color ÷ Modelo:Color = Modelo:Color	Modelo:Color − Modelo:Color × Modelo:Color = Modelo:Color	Modelo:Color − Modelo:Color × Modelo:Color = Modelo:Color	0 − Modelo:Color × 1 = −5
3	Modelo:Color ÷ Modelo:Color = Modelo:Color	Modelo:Color − Modelo:Color × Modelo:Color = Modelo:Color	Modelo:Color − Modelo:Color × Modelo:Color = Modelo:Color	1 − Modelo:Color × −5 = 21
4	Modelo:Color ÷ Modelo:Color = Modelo:Color	Modelo:Color − Modelo:Color × Modelo:Color = Modelo:Color	Modelo:Color − Modelo:Color × Modelo:Color = Modelo:Color	−5 − Modelo:Color × 21 = −26
5	Modelo:Color ÷ Modelo:Color = Modelo:Color	Modelo:Color − Modelo:Color × Modelo:Color = Modelo:Color	Modelo:Color − Modelo:Color × Modelo:Color = Modelo:Color	21 − Modelo:Color × −26 = Modelo:Color
6	Modelo:Color ÷ Modelo:Color = Modelo:Color	Modelo:Color − Modelo:Color × Modelo:Color = Modelo:Color	Modelo:Color − Modelo:Color × Modelo:Color = Modelo:Color	−26 − Modelo:Color × 47 = Modelo:Color

A maiores, os cocientes, en azul, son os coeficientes da fracción continua de Modelo:Sfrac = [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 $0\le r_{i+1}<|r_i|$ ten que ser substituída por unha desigualdade nos graos do polinomio $\mathrm{deg}{r}_{i+1}<\mathrm{deg}{r}_i.$ 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 $r_k.$ 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

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

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.

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

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.

$\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 ),$

Cálculo de inversos multiplicativos en aritmética modular

Números enteiros modulares

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

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

$ns+at=1$

Reducindo esta identidade módulo Modelo:Math dáse

$at\equiv 1modn.$

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

Extensións simples de corpos alxébricos

Exemplo

Por exemplo, se o polinomio usado para definir o corpo finito GF(2⁸) é Modelo:Math, e Modelo:Math é 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 2ⁿ, 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
		Modelo:Math	1	0
		Modelo:Math	0	1
1	Modelo:Math	Modelo:Math	1	Modelo:Math
2	Modelo:Math	Modelo:Math	Modelo:Math	Modelo:Math
3	Modelo:Math	Modelo:Math	Modelo:Math	Modelo:Math
4	Modelo:Math	Modelo:Math	Modelo:Math

Así, o inverso é Modelo:Math, como se pode confirmar multiplicando os dous elementos xuntos e tomando o resto por Modelo:Mvar 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.

$\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 ),$

Véxase tamén

Bibliografía

• Modelo:Cita libro 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. Modelo:ISBN. 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)