Algoritmo de Euclides estendido

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

O Algoritmo de Euclides estendido é uma extensão do algoritmo de Euclides, que, além de calcular o máximo divisor comum (MDC) entre a, b \in \mathbb{Z} , fornece os coeficientes \alpha, \beta \in \mathbb{Z} tais que \alpha a + \beta b = mdc(a, b) .

O algoritmo é utilizado, em especial, para o cálculo de inverso modular. Se a e b são coprimos, então \alpha
 é o inverso modular de a módulo b e \beta
 é o inverso modular de b módulo a . 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[editar | editar código-fonte]

O Algoritmo de Euclides nos fornece a seguinte propriedade: na k-ésima iteração, vale que

r_{k+1} = r_{k-1} - r_kq_k

onde q_k = \frac{r_{k-1}}{r_k} é uma divisão inteira.

O algoritmo acaba quando r_{k+1} = 0, definindo o resto atual como o máximo divisor comum: r_k = MDC(a,b).

Para estender o algoritmo, queremos também manter a seguinte propriedade:

r_k = au_k + bv_k

dessa forma, quando o algoritmo acabar, teremos valores u_k e v_k que satisfazem o teorema de Bézout.

Para isso, assuma que nós temos esses valores para a iteração k e para a iteração anterior, k-1: ou seja, assuma que já temos os valores que satisfazem as duas igualdades a seguir:

r_{k} = au_{k} + bv_{k} e r_{k-1} = au_{k-1} + bv_{k-1}

então, para o próximo resto, teremos

\begin{align}
r_{k+1} & = r_{k-1} - r_kq_k  \\
              & = (au_{k-1} + bv_{k-1}) - (au_{k} + bv_{k})q_k \\
              & = au_{k-1} - au_{k}q_k + bv_{k-1} - bv_{k}q_k \\
              & = a(u_{k-1} - u_{k}q_k) + b(v_{k-1} - v_{k}q_k) \\
              & = au_{k+1} + bv_{k+1} \\
\end{align}

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

u_{k+1} = u_{k-1} - u_{k}q_k

e

v_{k+1}  = v_{k-1} - v_{k}q_k

Perceba que os valores de Bézout também estão sendo totalmente definidos pelos valores das duas últimas iterações do algoritmo.

Dessa forma, para estender o Algoritmo de Euclides original, só precisamos guardar os valores referentes à essas duas sequências (v_k e u_{k}) além da que o original já guarda (a sequência r_k) e definir valores para que tenhamos igualdades válidas para k = 0 e para k = 1 (já que cada sequência é definida em termos de duas iterações anteriores).

No entanto, definir esses valores é fácil: podemos tomar

(r_0, u_0, v_0)  = (a, 1, 0), o que torna válida a igualdade para k = 0 (ou seja, r_0 = au_0 + bv_0)

e

(r_1, u_1, v_1)  = (b, 0, 1), o que torna válida a igualdade para k = 1 (ou seja, r_1 = au_1 + bv_1)

Um exemplo[editar | editar código-fonte]

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) = 120*(-9) + 47*23

O algoritmo[editar | editar código-fonte]

Código em JavaScript[editar | editar código-fonte]

/*********************************************
*  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++[editar | editar código-fonte]

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];
}

Referências[editar | editar código-fonte]

  • Coutinho, Severino Collier. Números inteiros e criptografia RSA. Rio de Janeiro: IMPA, 2005. 226 pp. ISBN 8524401249.
  • Knuth, D. E.. The art of computer programming: Seminumerical algorithms (em inglês). 3. ed. [S.l.]: Addilson-Wesley Publishing Company. vol. 2. ISBN 9780201896848.
Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.
Ícone de esboço Este artigo sobre Informática é um esboço. Você pode ajudar a Wikipédia expandindo-o.