Teorema Chinês do Resto

O teorema resolve sistemas de congruências com módulos coprimos, e sua importância prática vem de uma leitura estrutural: ele permite decompor um problema módulo $n$ em problemas independentes módulo os fatores de $n$.

Enunciado

Se $n_1, \dots, n_k$ são dois a dois coprimos, o sistema

$$x \equiv a_1 \pmod{n_1}, \quad \dots, \quad x \equiv a_k \pmod{n_k}$$

tem solução única módulo $N = n_1n_2\cdots n_k$.

Em linguagem de estruturas: existe um isomorfismo de anéis

$$\mathbb{Z}N \cong \mathbb{Z}{n_1}\times\cdots\times\mathbb{Z}_{n_k}$$

Ou seja, um número módulo $N$ é equivalente à tupla de seus restos. E como o isomorfismo preserva soma e produto, pode-se calcular componente a componente.

Construção

Seja $N_i = N/n_i$. Como $\gcd(N_i, n_i) = 1$, existe $M_i = N_i^{-1} \bmod n_i$. Então

$$x \equiv \sum_{i=1}^{k} a_i N_i M_i \pmod N$$

def crt(restos, modulos):
    N = 1
    for m in modulos:
        N *= m
    x = 0
    for a, m in zip(restos, modulos):
        Ni = N // m
        Mi = pow(Ni, -1, m)      # inverso modular (Python 3.8+)
        x += a * Ni * Mi
    return x % N

A ideia da construção: cada termo da soma vale $a_i$ módulo $n_i$ e zero módulo os demais, porque $N_i$ é múltiplo de todos os outros módulos.

Aceleração do RSA

Esta é a aplicação de maior impacto prático. A decifração RSA calcula $m = c^d \bmod n$ com $n = pq$ e $d$ do tamanho de $n$ — uma exponenciação cara.

Quem possui a chave privada conhece $p$ e $q$, e pode trabalhar separadamente:

$$m_p = c^{d \bmod (p-1)} \bmod p, \qquad m_q = c^{d \bmod (q-1)} \bmod q$$

e recombinar por CRT. Como as duas exponenciações são feitas com números de metade do tamanho, e o custo da exponenciação modular cresce cubicamente com o número de bits, o ganho é de cerca de quatro vezes.

Toda implementação séria de RSA usa isso — é por isso que a chave privada armazena $p$, $q$ e os expoentes reduzidos, e não apenas $d$.

Alerta de segurança: a otimização introduziu uma vulnerabilidade famosa. Se ocorrer uma falha de hardware durante apenas uma das duas exponenciações, o resultado recombinado permite fatorar $n$ com um único MDC (ataque de Bellcore). Implementações corretas verificam o resultado antes de devolvê-lo.

Aritmética de resíduos

O isomorfismo permite representar números grandes por tuplas de resíduos pequenos e operar em paralelo, sem propagação de vaivém entre posições.

É usado em processamento de sinais, em algumas arquiteturas de hardware criptográfico e em computação simbólica: para calcular um determinante inteiro enorme, calcula-se módulo vários primos pequenos e reconstrói-se por CRT, evitando aritmética de precisão arbitrária no meio do caminho.

Exemplo trabalhado

Resolver:

$$x \equiv 2 \pmod 3, \qquad x \equiv 3 \pmod 5, \qquad x \equiv 2 \pmod 7$$

$N = 105$, e $N_1 = 35$, $N_2 = 21$, $N_3 = 15$.

Inversos: $35 \equiv 2 \pmod 3$ e $2^{-1} \equiv 2 \pmod 3$, logo $M_1 = 2$. $21 \equiv 1 \pmod 5$, logo $M_2 = 1$. $15 \equiv 1 \pmod 7$, logo $M_3 = 1$.

$$x \equiv 2\cdot35\cdot2 + 3\cdot21\cdot1 + 2\cdot15\cdot1 = 140 + 63 + 30 = 233 \equiv 23 \pmod{105}$$

Verificando: $23 = 3\cdot7+2$ ✓, $23 = 5\cdot4+3$ ✓, $23 = 7\cdot3+2$ ✓.

Este é, essencialmente, o problema formulado por Sun Tzu no século III — daí o nome.

Aplicações em computação

RSA-CRT. Decifração e assinatura quatro vezes mais rápidas.

Compartilhamento de segredo. O esquema de Asmuth-Bloom usa CRT para dividir um segredo em partes.

Computação algébrica. Cálculo modular com reconstrução, evitando explosão de coeficientes intermediários.

Sincronização. Determinar quando eventos de períodos coprimos coincidem.

Fatoração e testes. Vários algoritmos trabalham módulo primos pequenos e recombinam.

Erros comuns

• Módulos não coprimos. O teorema exige coprimalidade dois a dois; sem ela, pode não haver solução.
• Esquecer a verificação no RSA-CRT, deixando o ataque de falha em aberto.
• Estouro ao calcular $a_iN_iM_i$ com módulos grandes; use inteiros de precisão arbitrária.
• Confundir a solução única módulo $N$ com solução única nos inteiros — há infinitas, todas congruentes.

Leituras recomendadas

• Shoup, capítulo 2 — CRT com a formulação algébrica.
• Menezes et al., capítulo 14 — CRT aplicado a implementações criptográficas eficientes.
• Boneh, DeMillo e Lipton, "On the Importance of Checking Cryptographic Protocols for Faults" — o artigo do ataque de Bellcore.

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.