Inverso Modular

Definição

Na aritmética modular, não temos uma operação de divisão. No entanto, temos inversos modulares. Um inverso multiplicativo modular de um número inteiro $a$ é um número inteiro $x$ de modo que $a \cdot x$ é igual a $1$ sob o módulo de algum número $m$. Para escrevê-lo de maneira formal: queremos encontrar um número inteiro $x$ no qual $$a \cdot x \equiv 1 \mod m.$$ Nota: $mod$ = % e $gcd$ = $mdc$. Também denotaremos $x$ como $a^{-1}$.

Devemos notar que o inverso modular nem sempre existe. Por exemplo, seja $m = 4$, $a = 2$. Ao verificar todos os valores possíveis com módulo $m$ deve ficar claro que é possível não encontrar $a^{-1}$ satisfazendo a equação acima. Pode-se provar que o inverso modular existe se, e somente se, $a$ e $m$ são primos entre si (ou seja, coprimos, o máximo divisor comum entre os dois é 1 ($\gcd/mdc(a, m) = 1$)).

Neste artigo, apresentamos dois métodos para encontrar o inverso modular, caso exista, e um método para encontrar o inverso modular para todos os números em tempo linear.

Inverso Modular usando o algoritmo de Euclides Estendido

Considere a seguinte equação (com $x$ e $y$ desconhecidos):

$$a \cdot x + m \cdot y = 1$$

Esta é uma equação diofantina linear com duas variáveis. Quando o $\ mdc(a, m) = 1$, a equação tem uma solução que pode ser encontrada usando o algoritmo de Euclides Estendido. O $\ gcd/mdc(a, m) = 1$ também é a condição para o inverso modular existir.

Agora, se usarmos o módulo $m$ de ambos os lados, podemos nos livrar de $m \cdot y$, e a equação se tornará:

$$a \cdot x \equiv 1 \mod m$$

Assim, o inverso modular de $a$ é $x$.

Implementação:

int x, y;
int g = euclides(a, m, x, y);  //algoritmo de euclides estendido
if (g != 1) {
    cout << "Sem solução!";
}
else {
    x = (x % m + m) % m;
    cout << x << endl;
}

Observe que nós modificamos x. O x resultante do algoritmo de Euclides pode ser negativo, portanto, x % m também pode ser negativo, precisamos adicionar m primeiro para torná-lo positivo.

Inverso Modular usando Exponenciação Binária

Outro método para encontrar o inverso modular é usar o teorema de Euler, no qual afirma que a seguinte congruência é verdadeira se $a$ e $m$ forem coprimos:

$$a^{\phi (m)} \equiv 1 \mod m$$

$\phi$ é a função totiente de Euler. Novamente, observe que $a$ e $m$ serem coprimos também é a condição para o inverso modular existir.

Se $m$ é um número primo, isso simplifica o pequeno teorema de Fermat:

$$a^{m - 1} \equiv 1 \mod m$$

Multiplique ambos os lados das equações acima por $a^{-1}$, e obtemos:

A partir desses resultados, podemos encontrar o inverso modular usando o algoritmo da exponenciação binária, que funciona em tempo $O(\log m)$.

Embora esse método seja mais fácil de entender do que o descrito no parágrafo anterior, no caso em que $m$ não seja um número primo, precisamos calcular a função de Euler, no qual envolve a fatoração de $m$, o que pode ser bem difícil. Se a fatoração de $m$ é conhecida, então a complexidade desse método é $O(\log m)$.

Encontrando o inverso modular para todos os números módulo $m$

O problema é: queremos calcular o inverso modular para cada número no intervalo $[1, m-1]$.

Aplicando os algoritmos descritos nas seções anteriores, podemos obter uma solução com complexidade $O(m \log m)$.

Aqui apresentamos um algoritmo melhor com complexidade $O(m)$. No entanto, para este algoritmo específico, é requerido que o módulo $m$ seja primo.

Denotamos como $\text{inv}[i]$ o inverso modular de $i$. Assim, para $i > 1$ a equação seguinte é válida:

$$\text{inv}[i] = - \left\lfloor \frac{m}{i} \right\rfloor \cdot \text{inv}[m \bmod i] \bmod m$$

Portanto, a implementação é:

inv[1] = 1;
for(int i = 2; i < m; ++i)
    inv[i] = (m - (m/i) * inv[m%i] % m) % m;

Prova

Nós temos: $$m \bmod i = m - \left\lfloor \frac{m}{i} \right\rfloor \cdot i$$ Tirando o módulo $m$ de ambos os lados, teremos: $$m \bmod i \equiv - \left\lfloor \frac{m}{i} \right\rfloor \cdot i \mod m$$ Multiplicando ambos os lados por $i^{-1} \cdot (m \bmod i)^{-1}$, temos: $$(m \bmod i) \cdot i^{-1} \cdot (m \bmod i)^{-1} \equiv -\left\lfloor \frac{m}{i} \right\rfloor \cdot i \cdot i^{-1} \cdot (m \bmod i)^{-1} \mod m,$$ simplificando: $$i^{-1} \equiv -\left\lfloor \frac{m}{i} \right\rfloor \cdot (m \bmod i)^{-1} \mod m,$$

Problemas

Recursos

  • Módulo de Congruência
  • Aritmética Modular - Khan