O Teorema Chinês do Resto (que será referido como CRT no restante deste artigo) foi descoberto pelo matemático chinês Sun Zi.
Seja $p = p_1 p_2 \cdots p_k$, onde $p_i$ são pares coprimos. Além de $p_i$, também recebemos um conjunto de equações de congruência $$\begin{align} a &\equiv a_1 \pmod{p_1} \\ a &\equiv a_2 \pmod{p_2} \\ &\ldots \\ a &\equiv a_k \pmod{p_k} \end{align}$$ onde $a_i$ são constantes dadas. A forma original do CRT afirma que o conjunto de equações de congruência dado sempre possui uma(exatamente uma) solução módulo $p$.
Uma conseqüência do CRT é que a equação $$ x \equiv a \pmod{p} $$ é equivalente ao sistema de equações $$\begin{align} x &\equiv a \pmod{p_1} \\ &\ldots \\ x &\equiv a \pmod{p_k} \end{align}$$ (Como acima, assuma que $p = p_1 p_2 \cdots p_k$ e $p_i$ são pares coprimos).
Outra consequência do CRT é que podemos representar grandes números usando uma array de pequenos números inteiros. Por exemplo, seja $p$ o produto dos primeiros $1000$ primos. A partir dos cálculos, $p$ irá ter por volta de $3000$ dígitos.
Qualquer número $a$ menor que $p$ pode ser representado como uma array $a_1, \ldots, a_k$, onde $a_i \equiv a \pmod{p_i}$. Mas, para fazer isso, obviamente precisamos saber como recuperar o número $a$ de sua representação. Nessa seção, nós discutimos Algoritmo de Garner, que pode ser usado para esse propósito. Procuramos uma representação na forma $$ a = x_1 + x_2 p_1 + x_3 p_1 p_2 + \ldots + x_k p_1 \ldots p_{k-1} $$ que é a representação(mixed radix) de $a$. O algoritmo de Garner calcula os coeficientes $x_1, \ldots, x_k$.
Deixe que $r_{ij}$ denote o inverso de $p_i$ módulo $p_j$ $$ r_{ij} = (p_i)^{-1} \pmod{p_j} $$ que pode ser encontrado usando o algoritmo descrito em Inverso Modular. Substituindo $a$ da representação "mixed radix" na primeira equação de congruência, obtemos $$ a_1 \equiv x_1 \pmod{p_1}. $$ Substituindo na segunda equação, então $$ a_2 \equiv x_1 + x_2 p_1 \pmod{p_2}. $$ que pode ser reescrita subtraindo $x_1$ e dividindo por $p_1$ para conseguir $$\begin{array}{rclr} a_2 - x_1 &\equiv& x_2 p_1 &\pmod{p_2} \\ (a_2 - x_1) r_{12} &\equiv& x_2 &\pmod{p_2} \\ x_2 &\equiv& (a_2 - x_1) r_{12} &\pmod{p_2} \end{array}$$ Similarmente, obtemos $$ x_3 \equiv ((a_3 - x_1) r_{13} - x_2) r_{23} \pmod{p_3}. $$
Agora, podemos ver claramente um padrão emergindo, que pode ser expresso pelo seguinte código:
for (int i = 0; i < k; ++i) {
x[i] = a[i];
for (int j = 0; j < i; ++j) {
x[i] = r[j][i] * (x[i] - x[j]);
x[i] = x[i] % p[i];
if (x[i] < 0)
x[i] += p[i];
}
}
Assim, aprendemos como calcular os coeficientes $x_i$ em tempo $O(k^2)$. O número $a$ agora pode ser calculado usando a fórmula mencionada anteriormente
$$ a = x_1 + x_2 p_1 + x_3 p_1 p_2 + \ldots + x_k p_1 \ldots p_{k-1} $$
Vale ressaltar que, na prática, quase sempre precisamos calcular a resposta usando grandes inteiros(big integers), mas os coeficientes $x_i$ geralmente podem ser calculados usando 'built-in types' e, portanto, o algoritmo de Garner é muito eficiente.
É conveniente implementar esse algoritmo usando Java, porque ele possui suporte para grandes inteiros usando a classe BigInteger.
Aqui, mostramos uma implementação que pode armazenar grandes números na forma de um conjunto de equações de congruência. Ele suporta adição, subtração e multiplicação. E com o algoritmo de Garner, podemos converter o conjunto de equações em um número inteiro único. Nesse código, usamos 100 números primos maiores que $10^9$, o que permite números tão grandes quanto $10^{900}$.
final int SZ = 100;
int pr[] = new int[SZ];
int r[][] = new int[SZ][SZ];
void init() {
for (int x = 1000 * 1000 * 1000, i = 0; i < SZ; ++x)
if (BigInteger.valueOf(x).isProbablePrime(100))
pr[i++] = x;
for (int i = 0; i < SZ; ++i)
for (int j = i + 1; j < SZ; ++j)
r[i][j] =
BigInteger.valueOf(pr[i]).modInverse(BigInteger.valueOf(pr[j])).intValue();
}
class Number {
int a[] = new int[SZ];
public Number() {
}
public Number(int n) {
for (int i = 0; i < SZ; ++i)
a[i] = n % pr[i];
}
public Number(BigInteger n) {
for (int i = 0; i < SZ; ++i)
a[i] = n.mod(BigInteger.valueOf(pr[i])).intValue();
}
public Number add(Number n) {
Number result = new Number();
for (int i = 0; i < SZ; ++i)
result.a[i] = (a[i] + n.a[i]) % pr[i];
return result;
}
public Number subtract(Number n) {
Number result = new Number();
for (int i = 0; i < SZ; ++i)
result.a[i] = (a[i] - n.a[i] + pr[i]) % pr[i];
return result;
}
public Number multiply(Number n) {
Number result = new Number();
for (int i = 0; i < SZ; ++i)
result.a[i] = (int)((a[i] * 1l * n.a[i]) % pr[i]);
return result;
}
public BigInteger bigIntegerValue(boolean can_be_negative) {
BigInteger result = BigInteger.ZERO, mult = BigInteger.ONE;
int x[] = new int[SZ];
for (int i = 0; i < SZ; ++i) {
x[i] = a[i];
for (int j = 0; j < i; ++j) {
long cur = (x[i] - x[j]) * 1l * r[j][i];
x[i] = (int)((cur % pr[i] + pr[i]) % pr[i]);
}
result = result.add(mult.multiply(BigInteger.valueOf(x[i])));
mult = mult.multiply(BigInteger.valueOf(pr[i]));
}
if (can_be_negative)
if (result.compareTo(mult.shiftRight(1)) >= 0)
result = result.subtract(mult);
return result;
}
}
Seja $p$ o produto de todos os números primos.
O esquema modular em si não permite representar números negativos. No entanto, pode-se observar que, se soubermos que os valores absolutos de nossos números são menores que $p / 2$, sabemos que deve ser negativo quando o número resultante for maior que $p / 2$. O condicional can_be_negative no código permite convertê-lo em negativo nesse caso.