miniaturadaimagem|Procedimento de algoritmo euclidiano estendido. O Algoritmo de Euclides estendido é uma extensão do algoritmo de Euclides, que, além de calcular o máximo divisor comum (MDC) entre fornece os coeficientes tais que
O algoritmo é utilizado, em especial, para o cálculo de inverso modular. Se e são coprimos, então é o inverso modular de módulo e é o inverso modular de módulo Essa propriedade é amplamente utilizada no estudo em Criptografia, mais especificamente, no processo de quebra de chaves privadas do método de encriptação RSA. Entendendo o algoritmo
O Algoritmo de Euclides nos fornece a seguinte propriedade: na k-ésima iteração, vale que
em que é uma divisão inteira.
O algoritmo acaba quando definindo o resto atual como o máximo divisor comum:
Para estender o algoritmo, queremos também manter a seguinte propriedade:
dessa forma, quando o algoritmo acabar, teremos valores e que satisfazem o teorema de Bézout.
Para isso, assuma que nós temos esses valores para a iteração e para a iteração anterior, ou seja, assuma que já temos os valores que satisfazem as duas igualdades a seguir:
e
então, para o próximo resto, teremos
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
e
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 ( e ) além da que o original já guarda (a sequência ) e definir valores para que tenhamos igualdades válidas para e para (já que cada sequência é definida em termos de duas iterações anteriores).
No entanto, definir esses valores é fácil: podemos tomar
o que torna válida a igualdade para (ou seja, ) e
o que torna válida a igualdade para (ou seja, )
Um exemplo
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) =
O algoritmo 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) }
Referências
Categoria:Teoria dos números Categoria:Algoritmos matemáticos