Wikipédia

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

Explorar interativamente o histórico
← Ver a alteração anteriorVer a alteração posterior →
Conteúdo apagado Conteúdo adicionado
VisualTexto wiki
format. <math> e pontuação, format. listas; Remoção de implementação redundante (uma só linguagem, ou pseudocódigo, é o suficiente)
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]].
</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 ==
 
O Algoritmo de Euclides nos fornece a seguinte propriedade: na ''k''-ésima iteração, vale que
 
<math display="block">r_{k+1} = r_{k-1} - r_kq_k</math>
 
ondeem que <math>q_k = \frac{r_{k-1}}{r_k}</math> é uma divisão inteira.
 
O algoritmo acaba quando <math>r_{k+1} = 0,</math>, definindo o resto atual como o máximo divisor comum: <math>r_k = MDC(a,b).</math>.
 
Para estender o algoritmo, queremos também manter a seguinte propriedade:
 
<math display="block">r_k = au_k + bv_k</math>
 
dessa forma, quando o algoritmo acabar, teremos valores <math>u_k</math> e <math>v_k</math> que satisfazem o [[Identidade de Bézout|teorema de Bézout]].
 
Para isso, assuma que nós temos esses valores para a iteração <math>k</math> e para a iteração anterior, <math>k-1:</math>: ou seja, assuma que já temos os valores que satisfazem as duas igualdades a seguir:
 
<math display="block">r_{k} = au_{k} + bv_{k}</math>
e
<math display="block">r_{k-1} = au_{k-1} + bv_{k-1}</math>
 
então, para o próximo resto, teremos
 
<math display="block">\begin{align}
r_{k+1} & = r_{k-1} - r_kq_k \\
& = (au_{k-1} + bv_{k-1}) - (au_{k} + bv_{k})q_k \\
Linha 39 ⟶ 37:
Ou seja, se a igualdade de Bézout vale para a iteração atual do algoritmo e para a iteração anterior, então, ela vale para a próxima e os valores de Bézout são
 
<math display="block">u_{k+1} = u_{k-1} - u_{k}q_k</math>
 
e
 
<math display="block">v_{k+1} = v_{k-1} - v_{k}q_k</math>
 
Perceba que os valores de Bézout também estão sendo totalmente definidos pelos valores das duas últimas iterações do algoritmo.
Linha 51 ⟶ 49:
No entanto, definir esses valores é fácil: podemos tomar
 
<math display="block">(r_0, u_0, v_0) = (a, 1, 0)</math>, o que torna válida a igualdade para <math>k = 0</math> (ou seja, <math>r_0 = au_0 + bv_0</math>)
 
o que torna válida a igualdade para <math>k = 0</math> (ou seja, <math>r_0 = au_0 + bv_0</math>) e
e
 
<math display="block">(r_1, u_1, v_1) = (b, 0, 1),</math>
 
<math>(r_1, u_1, v_1) = (b, 0, 1)</math>, o que torna válida a igualdade para <math>k = 1</math> (ou seja, <math>r_1 = au_1 + bv_1</math>)
 
== Um exemplo ==
Linha 86:
 
== O algoritmo ==
===CódigoUma implementação do algoritmo em [[JavaScript===]]:
<source lang="javascript">
/*********************************************
Linha 121:
}
</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;
}
 
*mdc = 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 }}
Obtida de "https://pt.wikipedia.org/wiki/Algoritmo_de_Euclides_estendido"