Algoritmo de Euclides estendido: diferenças entre revisões
Linha 5: | 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]]. |
</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 == |
== 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: |
Para encontrar o MDC(120,23) usando o [[Algoritmo de Euclides]], vamos efetuando divisões da seguinte forma: |
||
(1) 120/23 = 5 resta 5 |
(1) 120/23 = 5 resta 5 |
Revisão das 18h24min de 8 de outubro de 2014
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
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:
onde é o resto da divisão de por .
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: , onde é uma divisão inteira.
Desta forma, podemos substituir as variáveis para obter uma sequência: usando , e , temos a seguinte sequência:
que nos diz que para calcular o próximo resto, basta multiplicar o resto atual por 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 () é 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 (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
Código 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)
}
Código em C++
void euclidianoEstendido(int a, int b, int *alpha, int *beta, int *mdc) {
int x[2] = {1, 0};
int y[2] = {0, 1};
/* Enquanto o resto da divisão de a por b não for zero, eu continuo o algoritmo. */
while (a % b != 0) {
int quociente = a / b;
/* Atualizando os valores de a e b. */
int temp = a;
a = b;
b = temp % b;
/* Atualizando os valores de x e y. */
int X = x[0] - (x[1] * quociente);
int Y = y[0] - (y[1] * quociente);
x[0] = x[1];
x[1] = X;
y[0] = y[1];
y[1] = Y;
}
*gcd = b;
*alpha = x[1];
*beta = y[1];
}
Referências
- 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