Inverso Modular

Inverso modular: definição e algoritmo

Dado um inteiro a e um módulo n, o inverso modular é o inteiro a⁻¹ que faz valer a · a⁻¹ ≡ 1 (mod n). Ele aparece justamente quando mdc(a, n) = 1, e o algoritmo de Euclides estendido o encontra com rapidez.

Veja 3⁻¹ mod 7 = 5. Confere, já que 3 · 5 = 15 = 2 · 7 + 1. O teorema de Euler oferece outro caminho, a⁻¹ ≡ a^(φ(n)−1) (mod n), e se n = p por acaso for primo, o pequeno teorema de Fermat reduz isso a a⁻¹ ≡ a^(p−2) (mod p).

Aplicações

• RSA, onde a chave privada d nada mais é que o inverso e⁻¹ mod φ(n).
• Teorema Chinês dos Restos (CRT), em que combinar resíduos depende de inversos modulares.
• Hashing criptográfico e aritmética de curvas elípticas (ECC), ambos sobre corpos finitos.
• Álgebra computacional, quando se precisa resolver congruências lineares como a x ≡ b (mod n).

Perguntas frequentes

Quando o inverso não existe? Sempre que mdc(a, n) > 1. Pegue 6 módulo 9: não há inverso, pois mdc(6, 9) = 3.

O inverso é único? Módulo n, sim. Há exatamente um representante caindo no intervalo [0, n − 1].

Euclides ou Fermat, qual é mais rápido? O Euclides estendido lida com qualquer módulo e roda em O(log n). O atalho de Fermat só vale quando n é primo e recorre à exponenciação modular; também é O(log n), mas as constantes são maiores.