Fermat, Euler e Testes de Primalidade

2026-07-26 avancado teoria-dos-numeros criptografia, algoritmos

Fermat, Euler e Testes de Primalidade

Gerar uma chave RSA de 2048 bits exige encontrar dois primos de mil bits cada. Como se testa a primalidade de um número com 300 dígitos decimais? Certamente não por divisões sucessivas.

Pequeno teorema de Fermat

Se $p$ é primo e $\gcd(a,p)=1$:

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

Equivalentemente, $a^p \equiv a \pmod p$ para todo $a$.

Teorema de Euler

Generaliza para módulo composto. Se $\gcd(a,n)=1$:

$$a^{\varphi(n)} \equiv 1 \pmod n$$

Consequência operacional: expoentes podem ser reduzidos módulo $\varphi(n)$.

$$a^k \equiv a^{k \bmod \varphi(n)} \pmod n$$

É exatamente essa propriedade que faz o RSA funcionar. Com $n = pq$ e $ed \equiv 1 \pmod{\varphi(n)}$:

$$(m^e)^d = m^{ed} = m^{1 + k\varphi(n)} \equiv m \pmod n$$

Cifrar e decifrar são operações inversas por causa do teorema de Euler.

Teste de Fermat e seus limites

A recíproca do teorema de Fermat sugere um teste: se $a^{n-1} \not\equiv 1 \pmod n$ para algum $a$, então $n$ é composto — com certeza.

O problema é o inverso. Existem compostos que passam no teste para certas bases: os pseudoprimos de Fermat. Pior, os números de Carmichael (561, 1105, 1729, …) passam para toda base coprima. Existem infinitos deles, e por isso o teste de Fermat sozinho é insuficiente para criptografia.

Miller-Rabin

O teste padrão. Escreva $n-1 = 2^s d$ com $d$ ímpar. Para uma base $a$, $n$ é provável primo se

$$a^d \equiv 1 \pmod n \quad \text{ou} \quad a^{2^rd} \equiv -1 \pmod n \text{ para algum } 0 \le r < s$$

A ideia: num corpo, as únicas raízes quadradas de 1 são $\pm1$. Se aparecer outra raiz quadrada de 1 durante os quadrados sucessivos, $n$ não é primo.

import random

def miller_rabin(n, k=40):
    if n < 2:
        return False
    for p in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37):
        if n % p == 0:
            return n == p
    d, s = n - 1, 0
    while d % 2 == 0:
        d //= 2
        s += 1
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(s - 1):
            x = x * x % n
            if x == n - 1:
                break
        else:
            return False        # composto, com certeza
    return True                 # provável primo

Garantia: para $n$ composto, a probabilidade de passar numa rodada é no máximo $1/4$. Com $k$ rodadas independentes, o erro cai a $4^{-k}$.

Com $k=40$, o erro é abaixo de $10^{-24}$ — várias ordens de grandeza menor que a probabilidade de erro não detectado de memória RAM. É essa comparação que justifica usar um teste probabilístico em criptografia.

Note que o algoritmo é Monte Carlo unilateral: quando responde "composto", está sempre certo.

Versão determinística

Para $n < 3{,}3\times10^{24}$, testar as bases ${2,3,5,7,11,13,17,19,23,29,31,37}$ é determinístico — resultado verificado computacionalmente. É a escolha certa para inteiros de 64 bits.

O algoritmo AKS (2002) foi o primeiro teste determinístico de tempo polinomial sem hipóteses, resolvendo uma questão teórica de longa data. Na prática é lento demais e não substitui Miller-Rabin.

Densidade dos primos

Pelo teorema dos números primos, a quantidade de primos até $x$ é aproximadamente $x/\ln x$. Logo, perto de $N$, cerca de $1$ em $\ln N$ números é primo.

Para números de 1024 bits, $\ln N \approx 710$; considerando apenas ímpares, espera-se testar cerca de 355 candidatos. Com filtragem prévia por primos pequenos, o custo cai bastante — e é assim que a geração de chaves RSA leva segundos, não horas.

Fatoração: o problema difícil

Testar primalidade é fácil (polinomial); fatorar é difícil. Essa assimetria é o que sustenta o RSA.

Algoritmo	Complexidade	Uso
Divisão sucessiva	$O(\sqrt n)$	Números pequenos
Rho de Pollard	$O(n^{1/4})$	Fatores pequenos
Curvas elípticas	Subexponencial	Fatores médios
Crivo de corpo numérico	$\exp(O((\log n)^{1/3}))$	Recorde atual

O recorde público é a fatoração do RSA-250 (829 bits, em 2020), que consumiu cerca de 2700 anos de CPU. Chaves de 2048 bits estão muito além do alcance clássico.

Mas o algoritmo de Shor fatora em tempo polinomial num computador quântico suficientemente grande. É por isso que existe todo um esforço de padronização de criptografia pós-quântica — o NIST selecionou os primeiros algoritmos em 2022–2024, baseados em reticulados e não em fatoração.

Exemplo trabalhado

Verificar se $561$ é primo pelo teste de Fermat com $a=2$.

$561 = 3 \cdot 11 \cdot 17$, portanto é composto. Ainda assim, $2^{560} \equiv 1 \pmod{561}$ — ele passa no teste de Fermat. É o menor número de Carmichael.

Com Miller-Rabin: $560 = 2^4 \cdot 35$. Calculando $2^{35} \bmod 561 = 263$, que não é $1$ nem $560$. Elevando ao quadrado: $263^2 \equiv 166$, $166^2 \equiv 67$, $67^2 \equiv 1$. Apareceu $1$ vindo de $67$, que não é $\pm1$ — logo $67$ é uma raiz quadrada não trivial de 1, e $561$ é composto. Miller-Rabin detecta o que Fermat não vê.

Erros comuns

Usar teste de Fermat em criptografia, ignorando os números de Carmichael.
Poucas rodadas de Miller-Rabin.
Gerador não criptográfico para escolher as bases ou os candidatos a primo.
Implementar a primitiva à mão em vez de usar biblioteca auditada.
Confundir "provável primo" com "primo" em contexto que exige certeza matemática.

Leituras recomendadas

Menezes et al., capítulo 4 — geração de primos e testes, gratuito online.
Shoup, capítulo 10 — Miller-Rabin com a análise de erro completa.
Crandall e Pomerance, Prime Numbers: A Computational Perspective — a referência sobre algoritmos com primos.
Documentação do NIST sobre criptografia pós-quântica — o que muda com computação quântica.

Alfred J. Menezes and Paul C. van Oorschot and Scott A. Vanstone (1996). Handbook of Applied Cryptography. CRC Press. ISBN 9781439821916. Victor Shoup (2009). A Computational Introduction to Number Theory and Algebra. Cambridge University Press. DOI: 10.1017/cbo9780511814549. G. H. Hardy and E. M. Wright (2008). An Introduction to the Theory of Numbers. Oxford University Press. DOI: 10.1093/oso/9780199219858.001.0001.

Referências

Alfred J. Menezes; Paul C. van Oorschot; Scott A. Vanstone (1996). Handbook of Applied Cryptography. CRC Press.
Victor Shoup (2009). A Computational Introduction to Number Theory and Algebra. Cambridge University Press.
G. H. Hardy; E. M. Wright (2008). An Introduction to the Theory of Numbers. Oxford University Press.