Algoritmo de Euclides estendido: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Linha 5:
</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:
(1) 120/23 = 5 resta 5
| |||