Verificador de Número Primo

Primalidade e fatoração

A ideia mais simples de teste é a divisão de tentativa: se nenhum inteiro de 2 até √n divide n, então n é primo, basta ir até a raiz porque, se n = a·b, um dos fatores é ≤ √n. Isso é ótimo para números pequenos, mas fica lento para gigantes. Por isso a ferramenta usa Miller-Rabin determinístico, que decide a primalidade com poucas contas de exponenciação modular, e com as testemunhas certas dá resposta exata (não probabilística) até 10²⁴.

Já a fatoração usa a divisão sucessiva: retira-se o fator 2 enquanto possível, depois os ímpares 3, 5, 7… até a raiz quadrada do número que sobra; o que restar acima de 1 no final é o último fator primo. As multiplicidades viram os expoentes de saída. Também há duas verificações extras por raízes inteiras: n é quadrado perfeito se ⌊√n⌋² = n e cubo perfeito se ⌊∛n⌋³ = n.

• Divisão de tentativa só precisa ir até √n.
• Miller-Rabin determinístico: exato e rápido até 10²⁴.
• Fatoração por divisão sucessiva (2, depois ímpares até √n).
• Quadrado/cubo perfeito verificados por raízes inteiras.

Um primo e uma fatoração

Exemplo 1, testar 97: como √97 ≈ 9,8, basta checar os primos até 9, ou seja, 2, 3, 5 e 7. O 97 é ímpar, a soma dos algarismos (16) não é divisível por 3, ele não termina em 0 ou 5 e 97 = 7 × 13 + 6, então 7 também não divide. Nenhum fator até a raiz existe, logo 97 é primo.

Exemplo 2, fatorar 360: tirando o 2, 360 = 2 × 2 × 2 × 45 = 2³ × 45; depois 45 = 3 × 3 × 5 = 3² × 5. Assim, 360 = 2³ × 3² × 5. Como nem todos os expoentes são pares (há um 3 e um 1), 360 não é quadrado perfeito.

0, 1, o par 2 e onde primos importam

Alguns valores fogem à dicotomia primo/composto: 0 e 1 não são nem um nem outro, o 1 é chamado de unidade, e a definição de primo exige n > 1. O 2 é o único primo par, já que qualquer outro número par tem o 2 como fator. Uma consequência elegante da fatoração única: um número é quadrado perfeito exatamente quando todos os expoentes primos são pares, e cubo perfeito quando todos são múltiplos de 3.

Primos são a matéria-prima da teoria dos números e a base de boa parte da criptografia moderna: o RSA, por exemplo, apoia-se no fato de que multiplicar dois primos grandes é fácil, mas fatorar o produto de volta é computacionalmente caríssimo. Eles também aparecem em funções de hash, geradores pseudoaleatórios e códigos corretores de erros.

• 0 e 1 não são primos nem compostos (1 é unidade).
• 2 é o único primo par.
• Quadrado perfeito ⇔ todos os expoentes pares; cubo ⇔ múltiplos de 3.
• Usos: criptografia RSA, hashing, teoria dos números.