Aritmética Modular

Aritmética modular é a aritmética do relógio: depois de 12 vem 1 de novo. Formalmente, é a aritmética das classes de equivalência módulo $n$ — e é o ambiente natural de tudo que envolve ciclos, tabelas hash e criptografia.

Congruência

$$a \equiv b \pmod n \iff n \mid (a-b)$$

Esta é uma relação de equivalência, e portanto particiona $\mathbb{Z}$ em $n$ classes residuais. O conjunto delas é $\mathbb{Z}_n = {0,1,\dots,n-1}$.

Propriedades operatórias

Congruências podem ser somadas e multiplicadas:

$$a\equiv b,; c\equiv d \implies a+c \equiv b+d, \quad ac \equiv bd \pmod n$$

Consequência prática essencial: é possível reduzir a cada passo. Isso é o que impede o estouro numérico em cálculos modulares longos:

# ruim: o produto cresce sem controle
resultado = 1
for x in valores:
    resultado *= x
resultado %= n

# bom: reduz a cada passo
resultado = 1
for x in valores:
    resultado = (resultado * x) % n

Divisão não funciona diretamente. De $ac \equiv bc \pmod n$ não se conclui $a \equiv b$ — a menos que $\gcd(c,n)=1$. Para "dividir", multiplique pelo inverso modular, que só existe nessa condição.

Grupo multiplicativo

Os elementos invertíveis de $\mathbb{Z}_n$ são exatamente os coprimos com $n$. Eles formam o grupo $\mathbb{Z}_n^*$, cuja ordem é a função totiente de Euler:

$$\varphi(n) = n\prod_{p\mid n}\left(1-\frac1p\right)$$

Para $p$ primo, $\varphi(p) = p-1$ e todo elemento não nulo é invertível — ou seja, $\mathbb{Z}_p$ é um corpo. Esse fato é a razão de módulos primos serem preferidos em tantas aplicações.

Para $n = pq$ com $p,q$ primos distintos, $\varphi(n) = (p-1)(q-1)$ — a fórmula no coração do RSA.

Exponenciação modular rápida

Calcular $a^b \bmod n$ ingenuamente é inviável: $b$ pode ter centenas de bits. A exponenciação binária resolve em $O(\log b)$ multiplicações:

def pot_mod(base, exp, mod):
    resultado = 1
    base %= mod
    while exp > 0:
        if exp & 1:
            resultado = (resultado * base) % mod
        base = (base * base) % mod
        exp >>= 1
    return resultado

# em Python, embutido e otimizado:
pow(base, exp, mod)

Sem essa técnica não haveria criptografia de chave pública: $a^{65537} \bmod n$ com $n$ de 2048 bits leva microssegundos com exponenciação binária, e tempo geológico sem ela.

Alerta de segurança: a versão acima é vulnerável a ataques de canal lateral por tempo, já que o ramo depende do bit do expoente. Implementações criptográficas usam variantes de tempo constante (escada de Montgomery). Em código real, use uma biblioteca auditada — nunca implemente a primitiva você mesmo.

Teste de divisibilidade

As regras clássicas saem de congruências. Como $10 \equiv 1 \pmod 9$, temos $10^k \equiv 1$, logo um número é congruente à soma de seus dígitos módulo 9 — daí a regra do 9. Do mesmo modo, $10 \equiv -1 \pmod{11}$ dá a regra da soma alternada.

Aplicações em computação

Tabelas hash. h(k) = k % m. Escolher $m$ primo evita padrões quando as chaves têm estrutura regular.

Somas de verificação. ISBN, CPF, IBAN e o algoritmo de Luhn (cartões de crédito) são todos verificações modulares que detectam erros de digitação e transposição.

Buffers circulares. indice = (indice + 1) % tamanho.

Geradores pseudoaleatórios. Geradores congruenciais lineares são $x_{n+1} = (ax_n + c) \bmod m$.

Hashing de Rabin-Karp. Um hash rolante módulo um primo permite comparar substrings em tempo constante amortizado.

Criptografia. RSA, Diffie-Hellman, DSA e curvas elípticas operam em aritmética modular.

Redução de Montgomery. Técnica que substitui a divisão cara por deslocamentos, usada em toda biblioteca criptográfica séria.

Exemplo trabalhado

Calcular $3^{100} \bmod 7$.

Pelo pequeno teorema de Fermat, $3^6 \equiv 1 \pmod 7$. Como $100 = 6\cdot16 + 4$:

$$3^{100} = (3^6)^{16}\cdot3^4 \equiv 1^{16}\cdot81 \equiv 81 \bmod 7 \equiv 4$$

Verificando com exponenciação binária: $3^2=2$, $3^4 = 4$, $3^8 = 2$, ... o resultado bate.

Note como reduzir o expoente módulo $\varphi(n)$ transformou um cálculo enorme em trivial. É exatamente essa ideia que o RSA explora.

Erros comuns

• Resto negativo em linguagens com a convenção do C.
• Estouro ao multiplicar antes de reduzir; em linguagens com inteiros de 64 bits, o produto de dois números de 32 bits já pode estourar.
• Dividir em vez de multiplicar pelo inverso.
• Módulo não primo onde a primalidade é necessária.
• Implementar criptografia à mão, sem proteção contra canal lateral.

Leituras recomendadas

• Shoup, capítulos 2 a 4 — aritmética modular com foco computacional.
• Menezes, van Oorschot e Vanstone, Handbook of Applied Cryptography, capítulo 2 — gratuito online, com todos os algoritmos.
• Knuth, TAOCP volume 2 — aritmética de precisão arbitrária.
• Documentação do OpenSSL e da libsodium — como as primitivas são realmente implementadas.

Victor Shoup (2009). A Computational Introduction to Number Theory and Algebra. Cambridge University Press. DOI: 10.1017/cbo9780511814549. Alfred J. Menezes and Paul C. van Oorschot and Scott A. Vanstone (1996). Handbook of Applied Cryptography. CRC Press. ISBN 9781439821916.

Referências

1. Victor Shoup (2009). A Computational Introduction to Number Theory and Algebra. Cambridge University Press.
2. Alfred J. Menezes; Paul C. van Oorschot; Scott A. Vanstone (1996). Handbook of Applied Cryptography. CRC Press.