Fatoração em Primos

Prime factorisation and the fundamental theorem of arithmetic

The fundamental theorem of arithmetic says that every integer above 1 factors into primes in exactly one way, give or take the order of the factors. Euclid knew this around 300 BC, and Gauss gave it a rigorous proof in Disquisitiones Arithmeticae (1801). Take 60 = 2² · 3 · 5: no other combination of prime powers lands on 60. The plainest way to find it is trial division. You divide by 2, then 3, 5, 7, 11, and so on up to sqrt(n); if nothing divides by then, whatever is left is prime itself. Worst case, that costs O(sqrt n).

Once the numbers get really big, trial division gives way to faster algorithms. Pollard's rho handles medium-sized factors, then come the quadratic sieve and GNFS (general number field sieve), which is the best classical algorithm we have. On a quantum computer, Shor's algorithm would factor in polynomial time. For now RSA-2048 stays out of reach in practice, and that stubbornness is exactly what public-key cryptography is built on.

Applications

• RSA cryptography: its security rests on how hard it is to factor the product of two large primes.
• Counting divisors: when n = p₁^e₁ · p₂^e₂ ..., you get d(n) = ∏(eᵢ + 1). So 60 has 3 · 2 · 2 = 12 divisors.
• ENEM, vestibular and olympiad problems involving GCD, LCM and simplifying fractions.

FAQ

Why stop trial division at sqrt(n)? Suppose n = a · b with a ≤ b. Then a ≤ sqrt(n). Any factor sitting above sqrt(n) has a smaller partner that you would have caught already.

Is 1 a prime? No. Leaving 1 out is what keeps the factorisation in the fundamental theorem unique.

How big a number can this handle? Trial division clears numbers up to about 10¹² in a fraction of a second. Past that point you need the heavier machinery, like Pollard's rho or GNFS.