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

1 107 bytes removidos ,  18h26min de 8 de outubro de 2014
Movi parte do texto para a página que explica o algoritmo de euclides.
(Movi parte do texto para a página que explica o algoritmo de euclides.)
</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 ==
A ideia principal no [[Algoritmo de Euclides]] é que o MDC pode ser calculado recursivamente, usando o resto da divisão como entrada para o próximo passo, o que é embasado na seguinte propriedade do MDC:
 
<math>MDC(a,b) = MDC(b, r)</math>
 
onde <math>r</math> é o resto da divisão de <math>a</math> por <math>b</math>.
 
Isso quer dizer que o resto da divisão em uma chamada do algoritmo será usado como entrada para a próxima chamada.
 
Sabemos que esse resto é calculado da seguinte forma: <math>r = a - bq</math>, onde <math>q = \frac{a}{b}</math> é uma divisão inteira.
 
Desta forma, podemos substituir as variáveis para obter uma sequência: usando <math>a = r_{k-1}</math>, <math>b = r_k</math> e <math>r = r_{k+1}</math>, temos a seguinte sequência:
 
<math>r_{k+1} = r_{k-1} - r_kq</math>
 
que nos diz que para calcular o próximo resto, basta multiplicar o resto atual por <math>q = \frac{r_{k-1}}{r_k}</math> e depois subtrair do resto anterior.
 
Quando o próximo resto for igual a zero, o algoritmo termina a execução e o resto atual (<math>r_k</math>) é o máximo divisor comum.
 
Para encontrar o MDC(120,23) usando o [[Algoritmo de Euclides]], vamos efetuando divisões da seguinte forma:
283

edições