What is Prime Factorization?
Prime factorization (also called integer factorization) is the process of decomposing a positive integer into a product of prime numbers. By the Fundamental Theorem of Arithmetic, every integer greater than 1 has a unique prime factorization (up to the order of factors). For example, 60 = 2 × 2 × 3 × 5 = 2² × 3 × 5, and no other combination of primes produces 60.
Prime numbers themselves have the simplest factorization — they are their own sole prime factor. The number 1 is a special case: it has an empty factorization (it is the product of zero primes), which is why 1 is considered neither prime nor composite.
Finding Prime Factors
The most basic method is trial division: divide the number by 2 as many times as possible, then by 3, then by 5, and so on through successive primes up to √n. Each time a prime divides evenly, record it and continue with the quotient. For example, to factor 360: 360 ÷ 2 = 180, 180 ÷ 2 = 90, 90 ÷ 2 = 45, 45 ÷ 3 = 15, 15 ÷ 3 = 5, giving 360 = 2³ × 3² × 5.
For large numbers, more sophisticated algorithms are used: Pollard's rho algorithm, the quadratic sieve, and the general number field sieve (GNFS). The GNFS is the fastest known algorithm for factoring very large numbers and is used in attempts to factor RSA moduli.
Applications in Cryptography
The difficulty of factoring large numbers is the foundation of RSA encryption, one of the most widely used public-key cryptosystems. RSA relies on the fact that while it is easy to multiply two large primes (e.g., two 300-digit primes), factoring their 600-digit product is computationally infeasible with current technology. The security of online banking, secure communications, and digital signatures depends on this computational asymmetry.
Divisor Functions
Prime factorization enables computing important number-theoretic functions. If n = p₁a₁ × p₂a₂ × ... × pkak, then: the number of divisors τ(n) = (a₁+1)(a₂+1)...(ak+1), the sum of divisors σ(n) = Π(piai+1 − 1)/(pi − 1), and Euler's totient function φ(n) = n × Π(1 − 1/pi).
GCD and LCM
Prime factorization provides a direct way to compute the greatest common divisor (GCD) and least common multiple (LCM) of two numbers. The GCD uses the minimum exponent of each prime, and the LCM uses the maximum. For example, GCD(12, 18) = GCD(2²×3, 2×3²) = 2¹×3¹ = 6, and LCM(12, 18) = 2²×3² = 36.
Canonical Form
The canonical form of a prime factorization writes primes in ascending order with exponents: n = p₁a₁ × p₂a₂ × ... where p₁ < p₂ < ... This standard representation makes it easy to compare factorizations and compute number-theoretic functions. Highly composite numbers (like 360 = 2³ × 3² × 5 or 720 = 2⁴ × 3² × 5) have many small prime factors, giving them an unusually large number of divisors.