Algoritmo de Euclides estendido: diferenças entre revisões

1 781 bytes adicionados ,  19h07min de 8 de outubro de 2014
Formulação matemática da extensão do algoritmo.
(Movi parte do texto para a página que explica o algoritmo de euclides.)
(Formulação matemática da extensão do algoritmo.)
</math> é o inverso modular de <math>b </math> módulo <math>a </math>. Essa propriedade é amplamente utilizada no estudo em [[Criptografia]], mais especificamente, no processo de quebra de chaves privadas do [[RSA|método de encriptação RSA]].
== Entendendo o algoritmo ==
 
O Algoritmo de Euclides nos fornece a seguinte propriedade: na <math>k-ésima</math> iteração, vale que
 
<math>r_{k+1} = r_{k-1} - r_kq_k</math>
 
onde <math>q_k = \frac{r_{k-1}}{r_k}</math> é uma divisão inteira.
 
O algoritmo acaba quando <math>r_{k+1} = 0</math>, definindo o resto atual como o máximo divisor comum: <math>r_k = MDC(a,b)</math>.
 
Para estender o algoritmo, queremos também manter a seguinte propriedade:
 
<math>r_k = au_k + bv_k</math>
 
dessa forma, quando o algoritmo acabar, teremos valores <math>u_k</math> e <math>v_k</math> que satisfazem o teorema de Bézout.
 
Para isso, assuma que nós temos esses valores para a iteração <math>k</math> e para a iteração anterior, <math>k-1</math>: ou seja, assuma que já temos os valores que satisfazem as duas igualdades a seguir:
 
<math>r_{k} = au_{k} + bv_{k}</math>
e
<math>r_{k-1} = au_{k-1} + bv_{k-1}</math>
 
então, para o próximo resto, teremos
 
<math>r_{k+1} = r_{k-1} - r_kq_k
= (au_{k-1} + bv_{k-1}) - (au_{k} + 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}
</math>
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ézou são
 
<math>u_{k+1} = u_{k-1} - u_{k}q_k</math>
e
<math>v_{k+1} = v_{k-1} - v_{k}q_k</math>
 
Percebe 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 (<math>v_k</math> e <math>u_{k}</math>) além da que o original já guarda (a sequência <math>r_k</math>).
 
 
== Um exemplo ==
 
Para encontrar o MDC(120,23) usando o [[Algoritmo de Euclides]], vamos efetuando divisões da seguinte forma:
283

edições