Teorema Chinês do Resto

O Teorema Chinês do Resto (que será referido como CRT no restante deste artigo) foi descoberto pelo matemático chinês Sun Zi.

Formulação

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$.

Corolário

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).

Algoritmo de Garner

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.

Implementação do algoritmo de Garner

É 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;
    }
}

Nota sobre números negativos

Problemas