Testes de Primalidade

Este artigo descreve algoritmos para determinar se um número é primo ou não.

Trial Division

Por definição, um número primo não possui divisores além de $1$ e ele mesmo. Um número composto tem pelo menos um divisor adicional, vamos chamá-lo de $d$. Naturalmente $\frac{n}{d}$ também é um divisor de $n$. Note que $d \le \sqrt{n}$ ou $\frac{n}{d} \le \sqrt{n}$, portanto, um dos divisores $d$ e $\frac{n}{d}$ é $\le \sqrt{n}$. Podemos usar essa informação para checar a primalidade.

Tentamos encontrar um divisor não trivial, verificando se algum dos números entre $2$ e $\sqrt{n}$ é um divisor de $n$. Se for um divisor, então $n$ definitivamente não é primo, caso contrário ele será primo.

bool isPrime(int x) {
    for (int d = 2; d * d <= x; d++) {
        if (x % d == 0)
            return false;
    }
    return true;
}

Essa é a forma mais simples de checar se o número é primo. Você pode otimizar essa função, por exemplo, verificando apenas todos os números ímpares no loop, pois o único número primo par é 2. Várias dessas otimizações são descritas no artigo sobre fatoração de inteiros.

Teste de primalidade de Fermat

Este é um teste probabilístico.

O pequeno teorema de Fermat (veja também Euler's totient function) define que para um número primo $p$ e um inteiro coprimo $a$ (mdc(p,a) = 1) a equação a seguir é válida:

$$a^{p-1} \equiv 1 \bmod p$$

No geral, esse teorema não se aplica a números compostos.

Isso pode ser usado para criar um teste de primalidade. Escolhemos um número inteiro $2 \le a \le p - 2$, e verificamos se a equação é válida ou não. Se não for válida, e.g. $a^{p-1} \not\equiv 1 \bmod p$, saberemos que $p$ não poderá ser um número primo. Nesse caso, chamamos a base $a$ de "testemunha de Fermat" para a composição de $p$.

No entanto, também é possível que a equação seja válida para um número composto. Portanto, se a equação for válida, não temos uma prova de primalidade. Só podemos dizer que $p$ é provavelmente primo. Se o número for realmente composto, chamamos a base $a$ de mentirosa de Fermat.

Ao executar o teste para todas as bases possíveis $a$, podemos realmente provar que um número é primo. No entanto, isso não é feito na prática, pois requer mais esforço do que apenas fazer divisões de teste(trial division). Em vez disso, o teste será repetido várias vezes com opções aleatórias para $a$. Se não encontrarmos testemunha para a composição, é muito provável que o número seja de fato primo.

bool provavelPrimoFermat(int n, int iter=5) {
    if (n < 4)
        return n == 2 || n == 3;

    for (int i = 0; i < iter; i++) {
        int a = 2 + rand() % (n - 3);
        if (binpower(a, n - 1, n) != 1)   //exponenciação binária
            return false;
    }
    return true;
}

Usamos Exponenciação Binária para eficientemente calcular a exponenciação $a^{p-1}$.

Há uma má notícia: existem alguns números compostos em que $a^{n-1} \equiv 1 \bmod n$ é válido para todo $a$ coprimo até $n$, por exemplo, para o número $561 = 3 \cdot 11 \cdot 17$. Esses números são chamados de números de Carmichael. O teste de primalidade de Fermat pode identificar esses números apenas se tivermos uma sorte imensa de escolhermos uma base $a$ com $\gcd(a, n) \ne 1$.

O teste de Fermat ainda é utilizado na prática, pois é muito rápido e os números de Carmichael são muito raros. Existem apenas 646 números desse tipo abaixo de $10^9$.

Teste de primalidade de Miller-Rabin

O teste de Miller-Rabin amplia as idéias do teste de Fermat.

Para um número ímpar $n$, $n-1$ é par e podemos fatorar todas as potências de 2. Podemos escrever: $$n - 1 = 2^s \cdot d,~\text{with}~d~\text{odd}.$$

Isso nos permite fatorar a equação do pequeno teorema de Fermat: $$\begin{array}{rl} a^{n-1} \equiv 1 \bmod n &\Longleftrightarrow a^{2^s d} - 1 \equiv 0 \bmod n \\ &\Longleftrightarrow (a^{2^{s-1} d} + 1) (a^{2^{s-1} d} - 1) \equiv 0 \bmod n \\ &\Longleftrightarrow (a^{2^{s-1} d} + 1) (a^{2^{s-2} d} + 1) (a^{2^{s-2} d} - 1) \equiv 0 \bmod n \\ &\quad\vdots \\ &\Longleftrightarrow (a^{2^{s-1} d} + 1) (a^{2^{s-2} d} + 1) \cdots (a^{d} + 1) (a^{d} - 1) \equiv 0 \bmod n \\ \end{array}$$

Se $n$ é primo, então $n$ deve dividir um desses fatores. E no teste de Miller-Rabin primality verificamos exatamente essa afirmação, que é uma versão mais rígida da afirmação do teste de Fermat. Para uma base $2 \le a \le n-2$ verificamos se $$a^d \equiv 1 \bmod n$$ é válido, ou $$a^{2^r d} \equiv -1 \bmod n$$ é válido para algum $0 \le r \le s - 1$.

Se encontrarmos uma base $a$ que não satisfaça nenhuma das igualdades acima, então econtramos uma testemunha para a composição de $n$. Nesse caso, provamos que $n$ não é um número primo.

Semelhante ao teste de Fermat, também é possível que o conjunto de equações seja válido para um número composto. Nesse caso, a base $a$ é chamada de mentirosa(strong liar). Se uma base $a$ satisfaz as equações (uma delas), $n$ é apenas provavelmente primo. No entanto, não existem números como os números de Carmichael, onde todas as bases não triviais mentem. De fato, é possível mostrar que no máximo $\frac{1}{4}$ das bases podem ser fortes mentirosas. Se $n$ for composto, temos uma probabilidade de $\ge 75\%$ de que uma base aleatória nos diga que é composto. Fazendo várias iterações, escolhendo diferentes bases aleatórias, podemos dizer com uma probabilidade muito alta se o número é realmente primo ou se é composto.

Aqui está uma implementação para números inteiros de 64 bits.

using u64 = uint64_t;
using u128 = __uint128_t;

u64 binpower(u64 base, u64 e, u64 mod) {
    u64 result = 1;
    base %= mod;
    while (e) {
        if (e & 1)
            result = (u128)result * base % mod;
        base = (u128)base * base % mod;
        e >>= 1;
    }
    return result;
}

bool check_composite(u64 n, u64 a, u64 d, int s) {
    u64 x = binpower(a, d, n);
    if (x == 1 || x == n - 1)
        return false;
    for (int r = 1; r < s; r++) {
        x = (u128)x * x % n;
        if (x == n - 1)
            return false;
    }
    return true;
};

bool MillerRabin(u64 n) { // retorna true se n é Provavelmente primo, caso contrário retorna false.
    if (n < 4)
        return n == 2 || n == 3;

    int s = 0;
    u64 d = n - 1;
    while ((d & 1) == 0) {
        d >>= 1;
        s++;
    }

    for (int i = 0; i < iter; i++) {
        int a = 2 + rand() % (n - 3);
        if (check_composite(n, a, d, s))
            return false;
    }
    return true;
}

Antes do teste de Miller-Rabin, você pode testar adicionalmente se um dos primeiros números primos é um divisor. Isso pode acelerar muito o teste, já que a maioria dos números compostos possui divisores primos muito pequenos. Por exemplo, $88\%$ de todos os números têm fatores primos menores que $100$.

Versão determinística

Miller mostrou que é possível tornar o algoritmo determinístico apenas verificando todas as bases $\le O((\ln n)^2)$. Bach mais tarde deu um limite concreto, é necessário apenas testar todas as bases $a \le 2 \ln(n)^2$.

Este ainda é um número bastante grande de bases. Portanto, as pessoas investiram bastante poder computacional na busca de limites mais baixos. Acontece que, para testar um número inteiro de 32 bits, é necessário apenas verificar as 4 primeiras bases primárias: 2, 3, 5 e 7. O menor número composto que falha nesse teste é $3,215,031,751 = 151 \cdot 751 \cdot 28351$. E para testar números inteiros de 64 bits, basta verificar as 12 primeiras bases primárias: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, e 37.

Isso resulta na seguinte implementação determinística:

bool MillerRabin(u64 n) { // retorna true se n é primo, caso contrário retorna false.
    if (n < 2)
        return false;

    int r = 0;
    u64 d = n - 1;
    while ((d & 1) == 0) {
        d >>= 1;
        r++;
    }

    for (int a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
        if (n == a)
            return true;
        if (check_composite(n, a, d, r))
            return false;
    }
    return true;
}

Também é possível fazer a verificação com apenas 7 bases: 2, 325, 9375, 28178, 450775, 9780504 e 1795265022. No entanto, como esses números (exceto 2) não são primos, é necessário verificar adicionalmente se o número que está verificando é igual a qualquer divisor primário dessas bases: 2, 3, 5, 13, 19, 73, 193, 407521, 299210837.

Problemas