Números primos: definição, teste e utilidade em criptografia
O que é um número primo
Um número primo é um inteiro maior do que 1 que só é divisível por 1 e por si próprio. Os primeiros são 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 — e são infinitos, como Euclides demonstrou nos Elementos há mais de 2 300 anos. Os números que não são primos e são maiores do que 1 chamam-se compostos; podem sempre ser escritos como produto único de primos, um resultado conhecido como Teorema Fundamental da Aritmética.
O 1 não é primo, por convenção — se fosse, o teorema fundamental perderia unicidade (6 = 2×3 = 1×2×3 = 1×1×2×3...). O 2 é o único primo par; todos os outros primos são ímpares porque um número par maior do que 2 é divisível por 2.
Além do interesse puramente matemático, os primos são a base de praticamente toda a criptografia moderna. Quando abres um site com HTTPS, quando pagas com MB WAY ou quando o sistema bancário verifica a tua assinatura digital, há primos gigantes a proteger a comunicação. Curiosamente, é a dificuldade de encontrar primos em números grandes que faz com que a segurança funcione.
Como se testa a primalidade
Método ingénuo (divisões por tentativa):
Um número n é primo se não é divisível por nenhum d com 2 ≤ d ≤ √nBasta testar até √n porque, se n = a × b com a ≤ b, então a ≤ √n. Para n = 97, testas até √97 ≈ 9,85, ou seja, 2, 3, 5, 7 — todos falham, logo 97 é primo. Este método serve para números pequenos (até milhões) mas colapsa para números com mais de 20 dígitos.
Crivo de Erathóstenes — algoritmo elegante do século III a.C. para listar todos os primos até N:
- Escreve todos os inteiros de 2 a N
- Marca 2 como primo; risca todos os múltiplos de 2
- Passa ao próximo não riscado (3); marca como primo; risca múltiplos
- Repete até chegar a
√N
O que sobra são todos os primos até N. É rápido para N até 10 milhões.
Teste de Miller-Rabin — probabilístico, baseado no pequeno teorema de Fermat. Escolhe testemunhas aleatórias a e verifica congruências. Após k iterações, a probabilidade de erro é 4^(-k). Com 40 iterações, é praticamente impossível errar. É o algoritmo usado por bibliotecas como OpenSSL para gerar primos gigantes (2048+ bits) em segundos.
Exemplo prático
Verificar se 143 é primo. Calcula √143 ≈ 11,96. Testa divisão por 2 (falha, ímpar), 3 (1+4+3=8, não múltiplo de 3), 5 (não termina em 0 ou 5), 7 (143/7 = 20,43), 11 (143 = 11 × 13). Não é primo — é composto.
Fatorização única. 2024 = 2³ × 11 × 23. Cada inteiro tem uma única representação deste tipo, salvo ordem dos factores.
RSA em prática. Uma chave RSA de 2048 bits usa dois primos com aproximadamente 1024 bits cada. Multiplicá-los é trivial (nanossegundos); fatorizar o produto de volta é praticamente impossível com tecnologia clássica — as melhores estimativas apontam para milhares de anos de computação em supercomputadores. Quando geras uma chave GPG ou um certificado TLS, o teu computador gasta segundos a procurar dois primos suficientemente grandes.
Utilidade em criptografia
O RSA (Rivest-Shamir-Adleman, 1977) usa dois primos secretos p e q para gerar uma chave pública baseada em n = p × q. A segurança assenta na hipótese de que factorizar n é computacionalmente inviável. Este é o algoritmo por trás de HTTPS, GPG, assinatura digital do Cartão de Cidadão português e SEPA.
O Diffie-Hellman e as variantes em curvas elípticas (ECDH, usado por default em TLS 1.3) usam também aritmética modular sobre primos, mas com abordagens diferentes.
Ameaça futura: computadores quânticos poderão implementar o algoritmo de Shor e factorizar rapidamente. NIST está a padronizar criptografia pós-quântica (Kyber, Dilithium) para substituir RSA nos próximos 10-20 anos.
Erros comuns
Considerar 1 como primo. Não é, por convenção estabelecida no século XIX.
Assumir que primos são raros. Há infinitos, e são relativamente densos até 10 000 (mais de 1200 primos). Só ficam raros em escalas astronómicas.
Confundir “primo” com “impar”. Todos os primos maiores do que 2 são ímpares, mas nem todos os ímpares são primos (9 = 3×3, 15 = 3×5).
Testar divisibilidade até n/2. É correcto mas desnecessariamente lento. Basta até √n.
Usar testes determinísticos rápidos para números pequenos e probabilísticos para grandes sem entender. Miller-Rabin é probabilístico mas com iterações suficientes torna-se praticamente determinístico. Bibliotecas modernas fazem isto correctamente por defeito.
Assumir que factorizar é fácil. Para um número de 20 dígitos com dois factores primos próximos de 10 bilhões, um portátil demora horas. Para números RSA de 2048 bits, milénios.