Algoritmo de Euclides estendido: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
m →Referências: -typo; +{{Citar livro}} |
|||
Linha 1:
O '''Algoritmo de Euclides estendido''' é uma extensão do [[algoritmo de Euclides]], que, além de calcular o [[máximo divisor comum]] (MDC) entre <math>a, b \in \mathbb{Z} </math>, fornece os coeficientes <math>\alpha, \beta \in \mathbb{Z} </math> tais que <math>\alpha a + \beta b = mdc(a, b) </math>.
O algoritmo é utilizado, em especial, para o cálculo de inverso modular. Se <math>a </math> e <math>b </math> são [[Primos entre si|coprimos]], então <math>\alpha
</math> é o inverso modular de <math>a </math> módulo <math>b </math> e <math>\beta
</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 ==
Para encontrar o MDC(120,23) usando o [[Algoritmo de Euclides]], coloca-se da seguinte forma:
Linha 37 ⟶ 32:
== O algoritmo ==
===Código em JavaScript===
▲<syntaxhighlight lang="javascript">
/*********************************************
* Recebe dois inteiros não negativos a e b
Linha 74 ⟶ 66:
return [r, u, v]; // tais que a*u + b*v = r et r = pgcd (a, b)
}
</source>
===Código em C++===
<source lang="cpp">
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];
}
</source>
== Referências ==
* {{Citar livro|nome=Severino Collier |sobrenome=Coutinho |título=Números inteiros e criptografia RSA |local=Rio de Janeiro |editora=IMPA |ano=2005 |páginas=226 |id=ISBN 8524401249 }}
| |||