Fatorar Número

O que é fatoração em primos?

Fatorar um número quer dizer escrevê-lo como um produto de números primos. Pelo Teorema Fundamental da Aritmética, todo inteiro maior que 1 tem uma fatoração prima única. Veja o caso do 360: ele vira 2³ × 3² × 5.

É dessa fatoração que partem os algoritmos de MDC e MMC, a criptografia RSA e boa parte da teoria dos números.

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

O teorema fundamental da aritmética diz que todo inteiro maior que 1 admite uma única fatoração como produto de primos, a menos da ordem dos fatores. Então 60 = 2² · 3 · 5 e nenhuma outra combinação de potências de primos resulta em 60. O método mais simples é a divisão por tentativa: divide-se por 2 enquanto possível, depois 3, depois 5, 7, 11... até raiz(n) — se nada dividir até esse ponto, o que sobra é primo. Exemplo: 16 = 2⁴; 60 = 2 · 30 = 2 · 2 · 15 = 2² · 3 · 5.

Divisão por tentativa é O(raiz n) no pior caso. Para números de centenas de dígitos, usam-se algoritmos mais rápidos: rho de Pollard (bom para achar fatores pequenos), crivo quadrático e o GNFS (general number field sieve) — o melhor algoritmo clássico assintoticamente e o que detém os recordes públicos atuais de desafios RSA grandes.

Por que a fatoração importa

• Criptografia RSA depende da dificuldade prática de fatorar o produto de dois primos grandes. Chaves usuais hoje têm 2048 ou 4096 bits.
• Contagem de divisores: se n = p₁^e₁ · p₂^e₂ · ..., o número de divisores positivos é d(n) = (e₁ + 1)(e₂ + 1).... Para 60 = 2² · 3 · 5 dá 3 · 2 · 2 = 12 divisores.
• Soma de divisores e outras funções multiplicativas também são calculadas a partir da fatoração.
• Algoritmo de Shor em um computador quântico suficientemente grande fatoraria em tempo polinomial, quebrando o RSA — por isso a criptografia pós-quântica é hoje área ativa de pesquisa.