Algoritmo de Euclides estendido – Wikipédia, a enciclopédia livre

O Algoritmo de Euclides estendido é uma extensão do algoritmo de Euclides, que, além de calcular o máximo divisor comum (MDC) entre ${\displaystyle a,b\in \mathbb {Z} ,}$ fornece os coeficientes ${\displaystyle \alpha ,\beta \in \mathbb {Z} }$ tais que ${\displaystyle \alpha a+\beta b=mdc(a,b).}$

O algoritmo é utilizado, em especial, para o cálculo de inverso modular. Se ${\displaystyle a}$ e ${\displaystyle b}$ são coprimos, então ${\displaystyle \alpha }$ é o inverso modular de ${\displaystyle a}$ módulo ${\displaystyle b}$ e ${\displaystyle \beta }$ é o inverso modular de ${\displaystyle b}$ módulo ${\displaystyle a.}$ Essa propriedade é amplamente utilizada no estudo em Criptografia, mais especificamente, no processo de quebra de chaves privadas do método de encriptação RSA.

O Algoritmo de Euclides nos fornece a seguinte propriedade: na k-ésima iteração, vale que

$${\displaystyle r_{k+1}=r_{k-1}-r_{k}q_{k}}$$

em que ${\displaystyle q_{k}={\frac {r_{k-1}}{r_{k}}}}$ é uma divisão inteira.

O algoritmo acaba quando ${\displaystyle r_{k+1}=0,}$ definindo o resto atual como o máximo divisor comum: ${\displaystyle r_{k}=MDC(a,b).}$

Para estender o algoritmo, queremos também manter a seguinte propriedade:

$${\displaystyle r_{k}=au_{k}+bv_{k}}$$

dessa forma, quando o algoritmo acabar, teremos valores ${\displaystyle u_{k}}$ e ${\displaystyle v_{k}}$ que satisfazem o teorema de Bézout.

Para isso, assuma que nós temos esses valores para a iteração ${\displaystyle k}$ e para a iteração anterior, ${\displaystyle k-1:}$ ou seja, assuma que já temos os valores que satisfazem as duas igualdades a seguir:

$${\displaystyle r_{k}=au_{k}+bv_{k}}$$ e $${\displaystyle r_{k-1}=au_{k-1}+bv_{k-1}}$$

então, para o próximo resto, teremos

$${\displaystyle {\begin{aligned}r_{k+1}&=r_{k-1}-r_{k}q_{k}\\&=(au_{k-1}+bv_{k-1})-(au_{k}+bv_{k})q_{k}\\&=au_{k-1}-au_{k}q_{k}+bv_{k-1}-bv_{k}q_{k}\\&=a(u_{k-1}-u_{k}q_{k})+b(v_{k-1}-v_{k}q_{k})\\&=au_{k+1}+bv_{k+1}\\\end{aligned}}}$$

Ou seja, se a igualdade de Bézout vale para a iteração atual do algoritmo e para a iteração anterior, então, ela vale para a próxima e os valores de Bézout são

$${\displaystyle u_{k+1}=u_{k-1}-u_{k}q_{k}}$$

e

$${\displaystyle v_{k+1}=v_{k-1}-v_{k}q_{k}}$$

Perceba que os valores de Bézout também estão sendo totalmente definidos pelos valores das duas últimas iterações do algoritmo.

Dessa forma, para estender o Algoritmo de Euclides original, só precisamos guardar os valores referentes à essas duas sequências (${\displaystyle v_{k}}$ e ${\displaystyle u_{k}}$) além da que o original já guarda (a sequência ${\displaystyle r_{k}}$) e definir valores para que tenhamos igualdades válidas para ${\displaystyle k=0}$ e para ${\displaystyle k=1}$ (já que cada sequência é definida em termos de duas iterações anteriores).

No entanto, definir esses valores é fácil: podemos tomar

$${\displaystyle (r_{0},u_{0},v_{0})=(a,1,0),}$$

o que torna válida a igualdade para ${\displaystyle k=0}$ (ou seja, ${\displaystyle r_{0}=au_{0}+bv_{0}}$) e

$${\displaystyle (r_{1},u_{1},v_{1})=(b,0,1),}$$

o que torna válida a igualdade para ${\displaystyle k=1}$ (ou seja, ${\displaystyle r_{1}=au_{1}+bv_{1}}$)

Para encontrar o MDC(120,23) usando o Algoritmo de Euclides, vamos efetuando divisões da seguinte forma:

(1)    120/23 = 5 resta 5 (2)    23/5 = 4 resta 3 (3)    5/3 = 1 resta 2 (4)    3/2 = 1 resta 1 (5)    2/1 = 2 resta 0  

MDC(120,23) = 1 

Levando-se em conta apenas os restos encontrados, pode-se dizer que:

(1)     5 = 1*120 - 5*23 (2)     3 = 1*23 - 4*5   Substituindo o 5 temos         3 = 1*23 - 4*(1*120 - 5*23)         3 = -4*120 + 21*23 (3)     2 = 1*5 - 1*3    Substituindo o valor de 5 e 3 temos         2 = 1(1*120 - 5*23) - 1(-4*120 + 21*23)         2 = 5*120 - 26*23 (4)     1 = 1*3 - 1*2   Novamente substituindo 3 e 2         1 = 1(-4*120 + 21*23) - 1(5*120 - 26*23)         1 = -9*120 + 47*23 

portanto, x = -9 e y = 47 e temos:

MDC(120,23) = ${\displaystyle 120*(-9)+47*23}$ 

Uma implementação do algoritmo em JavaScript:

/********************************************* *  Recebe dois inteiros não negativos a e b * e devolve um vetor cuja primeira posição * é o mdc(a,b), a segunda posição é o valor u * e a terceira o valor v tais que *   a*u + b*v = mdc(a,b) **********************************************/ function euclides (a, b){ 	var r = a; 	var r1 = b; 	var u = 1; 	var v = 0; 	var u1 = 0; 	var v1 = 1;         // variáveis auxiliares para efetuar trocas 	var rs, us, vs, q;  	while (r1 != 0){ 		q = parseInt (r / r1); // pega apenas a parte inteira 		rs = r; 		us = u; 		vs = v; 		r = r1; 		u = u1; 		v = v1; 		r1 = rs - q *r1; 		u1 = us - q*u; 		v1 = vs - q*v1; 	}  	return [r, u, v]; // tais que a*u + b*v = r et r = pgcd (a, b) } 

• Coutinho, Severino Collier (2005). Números inteiros e criptografia RSA. Rio de Janeiro: IMPA. 226 páginas. ISBN 8524401249 
• Knuth, D. E. The art of computer programming. Seminumerical algorithms (em inglês). 2 3 ed. [S.l.]: Addilson-Wesley Publishing Company. ISBN 9780201896848 

Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o. v d e

Este artigo sobre informática é um esboço. Você pode ajudar a Wikipédia expandindo-o. v d e