Fatoração em Primos

Fatoração em primos e o teorema fundamental da aritmética

O teorema fundamental da aritmética diz que todo inteiro maior que 1 fatora em primos de um jeito só, fora a ordem dos fatores. Euclides já sabia disso por volta de 300 a.C., e Gauss deu uma demonstração rigorosa nas Disquisitiones Arithmeticae (1801). Pegue 60 = 2² · 3 · 5: nenhuma outra combinação de potências de primos chega a 60. O jeito mais direto de achar isso é a divisão por tentativa. Você divide por 2, depois 3, 5, 7, 11 e assim por diante até raiz(n); se nada dividir até aí, o que resta é primo. No pior caso, isso custa O(raiz n).

Quando os números ficam realmente grandes, a divisão por tentativa cede lugar a algoritmos mais rápidos. O rho de Pollard dá conta de fatores médios, e depois vêm o crivo quadrático e o GNFS (general number field sieve), o melhor algoritmo clássico que temos. Num computador quântico, o algoritmo de Shor fatoraria em tempo polinomial. Por ora o RSA-2048 segue fora de alcance na prática, e é justamente essa teimosia que sustenta a criptografia de chave pública.

Aplicações

• Criptografia RSA: a segurança vem de quão difícil é fatorar o produto de dois primos grandes.
• Contagem de divisores: quando n = p₁^e₁ · p₂^e₂ ..., você tem d(n) = ∏(eᵢ + 1). Logo, 60 tem 3 · 2 · 2 = 12 divisores.
• Questões de ENEM, vestibular e olimpíadas que envolvem MDC, MMC e simplificação de frações.

Perguntas frequentes

Por que parar a divisão por tentativa em raiz(n)? Suponha n = a · b com a ≤ b. Então a ≤ raiz(n). Todo fator que fica acima de raiz(n) tem um parceiro menor que você já teria pego antes.

O 1 é primo? Não. Deixar o 1 de fora é o que mantém única a fatoração do teorema fundamental.

Que tamanho de número essa calculadora aguenta? A divisão por tentativa resolve números até cerca de 10¹² em fração de segundo. Passando disso, entram os algoritmos pesados, como o rho de Pollard e o GNFS.