Prime factorisation

Euclid got most of the way there around 300 BCE. Elements Book VII, Proposition 30 — now known as Euclid's lemma — shows that if a prime divides a product it must divide one of the factors, and Propositions 31 and 32 establish that every composite number is measured by some prime. What Euclid never stated in the modern form is that the decomposition is unique.

The first clear statement of uniqueness came from the Persian mathematician Kamāl al-Dīn al-Fārisī, in a treatise on amicable numbers written around 1300. Putting it on a modern footing took another five hundred years: Carl Friedrich Gauss published Disquisitiones Arithmeticae in the summer of 1801, and Article 16 of that book contains the first proof of the uniqueness half of what is now called the fundamental theorem of arithmetic.

Knowing the factors exist is a different problem from finding them, and it turned out to be the harder one. Trial division is as old as the theorem, and every method since has been an attempt to beat it: Fermat's difference-of-squares trick, the congruence-of-squares ideas Legendre and Gauss developed from it, then in the twentieth century Pollard's p−1 and rho methods, Lenstra's elliptic-curve method, the quadratic sieve, and finally the number field sieve, first published in 1993.

That difficulty became load-bearing in 1977, when Rivest, Shamir and Adleman built a public-key cryptosystem on it. RSA-129, a 129-digit challenge number, fell in April 1994 to Derek Atkins, Michael Graff, Arjen Lenstra and Paul Leyland, who ran a multiple-polynomial quadratic sieve across roughly 1,600 computers belonging to some 600 volunteers; the decrypted message read "The Magic Words are Squeamish Ossifrage". RSA-250 followed in February 2020, and the 862-bit RSA-260 in September 2026. No classical algorithm has been published that factors every integer in polynomial time — Peter Shor found one in 1994, but only for a quantum computer. The difficulty of this page's job is a security assumption, not a theorem.

Key properties

• Fundamental theorem of arithmetic: every integer greater than 1 is a product of primes, and that product is unique up to the order of the factors.
• 1 is the empty product — it has no prime factors at all, which is one reason 1 is not counted as prime.
• Trial division only has to reach √n: if n = a × b with a ≤ b then a ≤ √n, so a factor below the square root is found first, or there is none.
• Every prime other than 2, 3 and 5 is congruent to 1, 7, 11, 13, 17, 19, 23 or 29 modulo 30, so a 30-wheel tests only 8 of every 30 candidate divisors.
• The number of divisors is the product of (exponent + 1): 360 = 2³ × 3² × 5 has 4 × 3 × 2 = 24 divisors.
• A number is a perfect square exactly when every exponent in its factorisation is even, and a perfect cube exactly when every exponent is a multiple of three.
• Euler’s totient is φ(n) = n × ∏(1 − 1/p) over the distinct primes p dividing n, so the factorisation yields it directly.
• No algorithm has been published that factors every integer in polynomial time on a classical computer; Shor’s 1994 quantum algorithm does so in polynomial time.

Where they turn up

• RSA encryption: a public key contains the product of two large primes, and the whole scheme rests on nobody being able to recover them from it.
• Reducing fractions and finding least common denominators — the first place most people meet factorisation, in primary-school arithmetic.
• Fast Fourier transforms: Cooley–Tukey splits a transform of composite length along its factors, while prime lengths need separate algorithms such as Rader’s or Bluestein’s, so FFT libraries factor the input length before choosing a strategy.
• Hash tables and linear congruential generators are given prime moduli so that a stride and the table size share no factor, which would otherwise shorten the cycle.
• Periodical cicadas in North America emerge on 13- and 17-year cycles, both prime. The usual explanation — that a prime cycle is hard for a shorter-cycled predator to track — is a hypothesis rather than a settled result.
• Gear design: tooth counts on a meshing pair are often chosen coprime (the "hunting tooth" convention) so the same two teeth do not meet on every revolution and wear unevenly.