Prime Factorization

What is prime factorization?

To factor a number is to write it as a product of prime numbers. By the Fundamental Theorem of Arithmetic, every integer greater than 1 has one unique prime factorization. Take 360 as an example: it works out to 2³ × 3² × 5.

This factorization is what GCD and LCM algorithms, RSA cryptography and much of number theory build on.

Prime factorisation and the fundamental theorem of arithmetic

The fundamental theorem of arithmetic states that every integer greater than 1 has a unique factorisation as a product of primes, up to the order of the factors. So 60 = 2² · 3 · 5 and no other prime-power combination produces 60. The simplest method to compute this is trial division: divide by 2 while possible, then 3, then 5, 7, 11... up to sqrt(n) — if nothing divides up to that point, what remains is itself prime. Example: 16 = 2⁴; 60 = 2 · 30 = 2 · 2 · 15 = 2² · 3 · 5.

Trial division is O(sqrt n) in the worst case. For numbers with hundreds of digits, faster algorithms are used: Pollard's rho (good for finding small factors), the quadratic sieve, and the general number field sieve (GNFS) — the asymptotically best classical algorithm and the one that holds the current public records for large RSA challenge numbers.

Why factorisation matters

• RSA cryptography relies on the practical difficulty of factoring the product of two large primes. Standard key sizes today are 2048 or 4096 bits.
• Counting divisors: if n = p₁^e₁ · p₂^e₂ · ..., the number of positive divisors is d(n) = (e₁ + 1)(e₂ + 1).... For 60 = 2² · 3 · 5 that gives 3 · 2 · 2 = 12 divisors.
• Sum of divisors and other multiplicative functions are computed from the factorisation as well.
• Shor's algorithm on a sufficiently large quantum computer would factor in polynomial time, breaking RSA — which is why post-quantum cryptography is now a major area of research.