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

766 bytes adicionados ,  06h15min de 28 de setembro de 2014
sem resumo de edição
m (→‎Referências: -typo; +{{Citar livro}})
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>.
{{sem notas|data=novembro de 2013}}
O '''Algoritmo de Euclides estendido''' é uma das formas de se encontrar o [[máximo divisor comum]] (MDC) de dois números inteiros. Nele, ao invés de retornar um valor único, fornece a [[combinação linear]], muito útil quando os [[inteiros]] são [[primos]] entre si. Por exemplo:
'''MDC(120,23)''' = 1
 
'''120''' e '''23''' são inteiros primos entre si porque não existe um divisor maior do que 1 que divida ambos. O [[Algoritmo]] de Euclides estendido retorna:
 
'''ax + by = MDC(a, b)'''
ou seja:
'''MDC(120,23)''' <math> = 120*(-9) + 23*47 </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:
 
== O algoritmo ==
===Código em JavaScript===
 
<syntaxhighlightsource lang="javascript">
Uma implementação do algoritmo em [[JavaScript]]:
 
 
<syntaxhighlight lang="javascript">
/*********************************************
* Recebe dois inteiros não negativos a e b
return [r, u, v]; // tais que a*u + b*v = r et r = pgcd (a, b)
}
</source>
</syntaxhighlight>
===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 }}
11

edições