Fatoração em Primos

Todo número inteiro maior que 1 pode ser escrito como produto de números primos, e essa decomposição é única — a menos da ordem dos fatores.

Esse resultado tem nome: teorema fundamental da aritmética. Ele garante que 60 é sempre 2 × 2 × 3 × 5, e nunca outra combinação de primos.

A ferramenta devolve os fatores, indica se o número é primo e lista todos os divisores — que são as combinações possíveis dos fatores encontrados.

O método é divisão sucessiva: divide-se por 2 enquanto for possível, depois testam-se os ímpares a partir de 3.

O teste para quando o divisor ultrapassa a raiz quadrada do que restou. Isso funciona porque, se um número tem um fator maior que sua raiz, o fator complementar é necessariamente menor — e já teria sido encontrado.

O que sobra ao fim, se for maior que 1, é primo e entra como último fator.

Essa parada na raiz quadrada é o que torna o método viável: para testar se 1.000.003 é primo, bastam cerca de mil divisões, não um milhão.

Multiplicar dois primos grandes é instantâneo. Recuperar os dois fatores a partir do produto é computacionalmente caro, e nenhum método rápido é conhecido para o caso geral.

Essa assimetria é a base da criptografia RSA: a chave pública é o produto, e a segurança está em ninguém conseguir fatorá-lo em tempo hábil.

Números de algumas dezenas de dígitos são fatorados rapidamente aqui. Chaves criptográficas reais têm centenas de dígitos, e por isso permanecem fora de alcance.