Prime factorization

The fundamental theorem of arithmetic states that every integer greater than 1 can be represented uniquely as a product of prime numbers, disregarding the order of the factors.¹ This uniqueness is what makes prime factorization a canonical representation. For instance, 12 = 2² × 3, and no other combination of primes yields 12. The theorem was known to Euclid and was rigorously proved by Carl Friedrich Gauss in his Disquisitiones Arithmeticae (1801).²

Computing the prime factorization of a number is straightforward for small integers using trial division, but becomes computationally hard as the number grows. The best-known general-purpose algorithm is the general number field sieve (GNFS), which has sub-exponential but super-polynomial complexity.³ This difficulty is the basis of the RSA cryptosystem, where the product of two large primes is made public while the primes themselves remain secret.⁴ Special-purpose algorithms, such as Pollard's rho and the elliptic curve method, are efficient for numbers with small factors.

Prime factorization is used to compute greatest common divisors, least common multiples, and to simplify fractions. It also appears in the study of perfect numbers, where the Euclid–Euler theorem characterizes even perfect numbers via Mersenne primes.⁵ In cryptography, the security of RSA relies on the practical difficulty of factoring large semiprimes. Factorization also plays a role in computer science, such as in hash functions and in the analysis of algorithms.

Prime factorization has surprising connections to other fields. For example, the fundamental theorem of arithmetic fails in certain rings of algebraic integers, such as ℤ[√−5], where 6 = 2 × 3 = (1+√−5)(1−√−5).⁶ The concept of prime factorization extends to ideals in number theory, where unique factorization is restored. Also, the prime factorization of a number can be encoded in its radical, which is the product of distinct primes, used in the abc conjecture. Historically, the sieve of Eratosthenes (c. 200 BC) is an early method for finding primes, but it does not directly factor numbers.

Prime number

An integer greater than 1 that has no positive divisors other than 1 and itself.

Fundamental theorem of arithmetic

The statement that every integer greater than 1 has a unique prime factorization.

RSA

A public-key cryptosystem whose security relies on the difficulty of factoring large semiprimes.

General number field sieve

The most efficient known algorithm for factoring large integers.