Inverso multiplicativo modulo n

O inverso multiplicativo de um inteiro modulo n é o resíduo inverse que satisfaz inteiro vezes inverse congruente a um modulo n. Esse inverse existe se e somente se o inteiro e o módulo forem coprimos — o máximo divisor comum vale um. Tutoriais de criptografia, etapas de chave privada RSA, divisão modular em programação competitiva e cálculos em grupos cíclicos precisam dessa operação, mas muitas linguagens só expõem um GCD binário e deixam os coeficientes de Bézout com você.

O que é um inverso multiplicativo modulo n e quando ele existe

Na aritmética comum todo número não nulo tem inverso multiplicativo: divida por ele e obtém um. Na aritmética modular a mesma ideia vira uma congruência. Dizemos que inverse é um inverso multiplicativo de um inteiro modulo n quando o inteiro vezes inverse deixa resto um ao dividir pelo módulo.

Como os resíduos reiniciam a cada n passos, nem todo inteiro tem tal inverse. O obstáculo é teórico-numérico, não de ponto flutuante: se d é o gcd do inteiro e do módulo e d é maior que um, então o inteiro vezes qualquer candidato é múltiplo de d, de modo que o produto nunca pode ser congruente a um, que não é múltiplo de d.

Por outro lado, a identidade de Bézout garante inteiros x e y com inteiro vezes x mais módulo vezes y igual a um exatamente quando esse gcd é um, e reduzir x modulo n produz o inverse. Engenheiros encontram essa condição ao dividir em um anel finito, ao escolher expoentes de decriptação RSA que invertem o expoente público modulo phi de N, ao desfazer multiplicações modulares em pipelines de hash ou ao resolver congruências lineares em programação competitiva.

Devolver um erro explícito quando o par não é coprimo é mais útil do que uma falha silenciosa: o cliente descobre que não existe inverse e pode ramificar pelo gcd em vez de adivinhar qual biblioteca devolveu um resíduo errado. A calculadora trata portanto um par não coprimo como entrada inválida, em vez de inventar um inverse provisório que quebraria qualquer verificação posterior da congruência definidora.

Como esta calculadora executa o algoritmo de Euclides estendido

A implementação primeiro reduz o inteiro à classe de resíduo não negativa residue em zero até n menos um e depois aplica o algoritmo de Euclides estendido ao par residue e modulus. Cada passo registra o quociente inteiro e atualiza os coeficientes de Bézout de modo que, ao terminar, o coeficiente de residue vezes residue mais um coeficiente do módulo iguala o gcd. Se o gcd for um, o coeficiente de residue é reduzido ao intervalo de zero a n menos um e devolvido como inverse.

Os valores absolutos são limitados a um trilhão para que todo dobramento intermediário do produto modular fique dentro da faixa de inteiros seguros do JavaScript. Inteiros negativos são aceitos e reduzidos antes do laço euclidiano, então uma entrada de menos três modulo onze é tratada como residue oito e invertida nessa classe.

Uso prático, limites, preços e entrega

Use a ferramenta do navegador quando quiser um inverse rápido ao ler uma nota de cripto, conferir uma congruência de dever de casa ou depurar um passo de multiplicação modular. As entradas aceitas são inteiros cujo valor absoluto é no máximo um trilhão e módulos de dois a um trilhão. Os resultados são determinísticos: o mesmo par sempre produz o mesmo inverse e o mesmo campo check.

Mantenha o par dentro dos limites publicados, trate o erro de não coprimos como resultado de primeira classe nos seus testes e você obtém um inverse reproduzível para deveres, plugins LMS e workers na borda sem montar um sistema de álgebra computacional próprio.