Princípio do Algoritmo:
O Algoritmo de Euclides Estendido não apenas calcula o máximo divisor comum mdc(a, m) de dois inteiros a e m, mas também encontra inteiros x e y tais que ax + my = gcd(a, m)。
Esta é uma aplicação da identidade de Bézout.
Passos do Algoritmo:
- Algoritmo de Euclides:Calcular mdc(a, m) usando o algoritmo de divisão, registrando o quociente e o resto em cada passo.
- Substituição Reversa:A partir do último passo, substitua reversamente para expressar cada resto como uma combinação linear de a e m.
- Resolução dos Coeficientes:Finalmente, obtenha os coeficientes x e y satisfazendo ax + my = mdc(a, m).
Inverso Modular:
Quando mdc(a, m) = 1 (ou seja, a e m são coprimos), existe um inverso multiplicativo de a módulo m, denotado como a-1 mod m. Neste caso, x é o inverso modular, satisfazendo a × x ≡ 1 (mod m)。
Se x for negativo, ele precisa ser ajustado para um valor positivo: x' = x mod m.
Aplicações:
- Criptografia:Calcular a chave privada no algoritmo RSA requer encontrar o inverso modular.
- Problemas de Teoria dos Números:Resolver congruências lineares da forma ax ≡ b (mod m).
- Combinatória:Cálculo Combinatório Modular (Teorema de Lucas, etc.)
- Programação Competitiva:Cálculo rápido de inverso modular para evitar problemas de precisão da divisão
Complexidade de Tempo:
O(log min(a, m)), igual ao Algoritmo de Euclides
Identidade de Bézout:
Para quaisquer inteiros a e m, existem inteiros x e y tais que ax + my = mdc(a, m). Esses coeficientes x e y podem ser eficientemente calculados usando o Algoritmo de Euclides Estendido.