Prime Factorization

1. What is Prime Factorization

Prime factorization is the process of expressing a positive integer greater than 1 as a product of prime numbers. For example, 360 = 2³ × 3² × 5. This is not an optional mathematical trick — it reveals the fundamental structure of an integer, much like a molecular formula reveals a substance's atomic composition.

The Fundamental Theorem of Arithmetic

This theorem has two critical parts:

• Existence — every integer > 1 can be decomposed into a product of primes (if it is itself prime, the product has a single factor).
• Uniqueness — this decomposition is essentially unique (ignoring the ordering of factors).

Historical Context

Euclid (~300 BC) first established existence in his Elements, Book IX: every composite number is divisible by some prime. However, he did not prove uniqueness.

The rigorous proof of uniqueness came nearly two millennia later, when Carl Friedrich Gauss published it in his landmark 1801 work Disquisitiones Arithmeticae. This treatise laid the foundation of modern number theory.

Why Does Uniqueness Matter?

If prime factorization were not unique, the entire edifice of number theory would collapse. For instance:

• GCD (Greatest Common Divisor) and LCM (Least Common Multiple) computations would become ambiguous.
• The security assumptions of RSA encryption would not hold.
• Reducing fractions could yield different "simplest forms."

In fact, in certain algebraic structures (such as Z[√-5]), unique factorization genuinely fails — this is precisely what motivated Ernst Kummer and Richard Dedekind to develop ideal theory in the 19th century.

2. Step-by-Step Algorithm: Trial Division

Trial division is the oldest and most intuitive prime factorization algorithm. Its core idea is beautifully simple: start with the smallest prime and try dividing repeatedly.

Algorithm Steps

1. Start with the smallest prime, p = 2.
2. If n is divisible by p (n mod p = 0), then p is a prime factor of n. Record p and set n = n / p.
3. Repeat step 2 until n is no longer divisible by p.
4. Advance p to the next prime (3, 5, 7, 11, ...) and return to step 2.
5. Stop when p × p > n. If n > 1 at this point, then n itself is a prime factor.

Why We Only Need to Check Up to √n

This is a critical optimization with a clean mathematical proof:

This means if no factor is found in the range 2 to √n, then n must be prime. This reduces the search space from n to √n.

Time Complexity

Trial division runs in O(√n) time. For n = 10¹², we check at most ~10⁶ divisors — modern computers handle this in milliseconds. But for n = 10¹⁰⁰ (like RSA keys), √n = 10⁵⁰, which no supercomputer could finish within the age of the universe.

Code Implementation (JavaScript)

Complete Walkthrough with 360

Result: 360 = 2³ × 3² × 5

3. Famous Algorithms for Large Numbers

Trial division works well for small numbers, but when numbers grow to dozens or hundreds of digits, we need far more efficient algorithms. Here are the key algorithms in historical order.

Sieve of Eratosthenes

Inventor: Eratosthenes of Cyrene, circa 240 BC — also famous for accurately measuring the Earth's circumference.

Idea: Rather than testing individual numbers for primality, systematically sieve out all composites. Starting from 2, mark all multiples of 2 as composite; find the next unmarked number (3) and mark its multiples; and so on. All remaining unmarked numbers are prime.

Use in factorization: We can pre-generate a table of primes using the sieve, then perform trial division using only primes, skipping all composite divisors.

Fermat's Factorization

Inventor: Pierre de Fermat, 1643.

Core idea: Express n as a difference of two squares: n = a² - b² = (a + b)(a - b). Start at a = ⌈√n⌉ and check whether a² - n is a perfect square.

Strength: When n's two factors are close to √n (e.g., the two prime factors of an RSA semiprime are similar in size), Fermat's method finds the factorization extremely quickly. This is precisely why RSA requires its two prime factors to differ significantly in magnitude.

Pollard's Rho Algorithm

Inventor: John Pollard, published 1975.

Core idea: Exploit a pseudo-random sequence and the birthday paradox. Define an iteration function f(x) = (x² + c) mod n, maintain two iterators at different speeds (Floyd's cycle detection), and compute the GCD of their difference with n. When the GCD is neither 1 nor n, we have found a non-trivial factor.

Complexity: Expected O(n^1/4) — vastly better than trial division's O(n^1/2). Excellent for numbers in the 20-25 digit range.

Code: Pollard's Rho (JavaScript)

Quadratic Sieve and General Number Field Sieve (GNFS)

The Quadratic Sieve, proposed by Carl Pomerance in 1981, was the first practical sub-exponential factoring algorithm. It works by finding "smooth numbers" (numbers with only small prime factors) in a sieving interval, then constructing a system of linear equations to extract factors of n.

The General Number Field Sieve (GNFS) is the fastest known algorithm for factoring large integers. It operates in algebraic number fields using lattice reduction and sophisticated sieving strategies. In 2020, GNFS successfully factored RSA-250 (829 binary digits, 250 decimal digits), setting the current world record.

4. Key Formulas and Properties

Once we have the prime factorization n = p₁^a₁ × p₂^a₂ × ... × p_k^a_k, we can directly compute many important number-theoretic functions.

Divisor Count Function τ(n)

Why does this formula work? (Combinatorial argument)

Any divisor d of n has the form d = p₁^b₁ × p₂^b₂ × ... × p_k^b_k, where 0 ≤ b_i ≤ a_i. For each prime factor p_i, the exponent b_i has (a_i + 1) choices (from 0 through a_i). By the multiplication principle, the total number of divisors equals the product of choices for each prime factor.

Example: 360 = 2³ × 3² × 5¹, so τ(360) = (3+1)(2+1)(1+1) = 4 × 3 × 2 = 24.

Sum of Divisors Function σ(n)

Derivation: For each prime factor p_i, its contribution to divisors is p_i⁰ + p_i¹ + ... + p_i^a_i. This is a geometric series with sum (p_i^a_i+1 - 1) / (p_i - 1). Since the sum-of-divisors function is multiplicative, the total equals the product of each prime's contribution.

Example: σ(360) = (2⁴-1)/(2-1) × (3³-1)/(3-1) × (5²-1)/(5-1) = 15 × 13 × 6 = 1170.

Euler's Totient Function φ(n)

Who: Leonhard Euler, introduced in 1763. Euler's totient φ(n) counts the number of positive integers from 1 to n that are coprime to n.

Why it matters:

• Heart of RSA encryption: key generation relies on φ(n) = (p-1)(q-1).
• Euler's theorem: if gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n) — a generalization of Fermat's little theorem.
• Group theory: φ(n) equals the order of the multiplicative group of integers modulo n, (ℤ/nℤ)*.

Example: φ(360) = 360 × (1 - 1/2) × (1 - 1/3) × (1 - 1/5) = 360 × 1/2 × 2/3 × 4/5 = 96.

Formula Summary Table

5. Real-World Applications

RSA Cryptography

RSA (Rivest, Shamir, Adleman, 1977) is a cornerstone of modern internet security. Its security relies entirely on the difficulty of factoring large integers.

How it works: Choose two large primes p and q (each ~150-300 digits), compute n = p × q. The public key contains n, but recovering p and q from n (i.e., factoring n) is computationally infeasible. Decryption requires φ(n) = (p-1)(q-1), and computing φ(n) is equivalent to factoring n.

Current record: RSA-250 (250 decimal digits, 829 binary digits) was factored in 2020, requiring approximately 2,700 CPU-years of computation. RSA-2048 (617 decimal digits) used in practice is considered safe with current technology.

Quantum threat: Peter Shor's 1994 quantum algorithm can factor large integers in polynomial time. If large-scale quantum computers become reality, RSA will be broken — this drives active research in post-quantum cryptography.

GCD and LCM Computation

Given the prime factorizations of two numbers:

• GCD = product of shared primes with minimum exponents
• LCM = product of all primes with maximum exponents

Example: 360 = 2³ × 3² × 5, and 150 = 2 × 3 × 5²

• GCD(360, 150) = 2¹ × 3¹ × 5¹ = 30
• LCM(360, 150) = 2³ × 3² × 5² = 1800

Simplifying Fractions

Reducing a fraction a/b to lowest terms is essentially computing GCD(a, b) and dividing both by it. Prime factorization lets us visually see which factors cancel. For example: 120/360 = (2³×3×5) / (2³×3²×5) = 1/3.

Applications in Number Theory

• Perfect Numbers: Numbers where σ(n) = 2n. Euler proved all even perfect numbers have the form 2^p-1(2^p - 1), where 2^p - 1 is a Mersenne prime.
• Amicable Numbers: Two numbers a, b where σ(a) - a = b and σ(b) - b = a. The smallest pair is 220 and 284.
• Discrete Logarithms in Cryptography: Prime factorization is closely related to the discrete logarithm problem, affecting the security of Diffie-Hellman and ElGamal encryption.

6. Famous Numbers and Stories

Mersenne Primes

Primes of the form M_p = 2^p - 1 are named after French friar Marin Mersenne (1588-1648). In 1644, Mersenne claimed to list all p ≤ 257 for which M_p is prime — although his list had several errors, it inspired centuries of research.

Why they're special: Mersenne primes are the source of the largest known primes. The current record holder is 2^82,589,933 - 1 (approximately 24.9 million digits), discovered by the GIMPS (Great Internet Mersenne Prime Search) project in 2018. GIMPS is a distributed computing project that anyone can contribute to.

Connection to perfect numbers: The Euclid-Euler theorem states that every Mersenne prime M_p yields an even perfect number 2^p-1 × M_p.

Fermat Numbers

Numbers of the form F_n = 2²ⁿ + 1. Fermat observed that F₀=3, F₁=5, F₂=17, F₃=257, F₄=65537 are all prime, and conjectured that all Fermat numbers are prime.

The counterexample: Leonhard Euler proved in 1732 that F₅ = 4,294,967,297 = 641 × 6,700,417, decisively refuting Fermat's conjecture. Every Fermat number tested since (F₅ through F₃₂) has been shown composite or remains of unknown primality. No Fermat prime beyond F₄ has ever been found.

A surprising connection: Gauss proved that a regular n-gon can be constructed with compass and straightedge if and only if n is a power of 2 times a product of distinct Fermat primes. This is why the regular 17-gon (F₂=17) is constructible but the regular 7-gon is not.

Twin Prime Conjecture

The conjecture states that there are infinitely many "twin primes" — pairs of primes differing by 2, such as (3,5), (11,13), (29,31), (41,43).

This conjecture remains unproven. In 2013, Yitang Zhang proved there are infinitely many prime pairs differing by at most 70 million — a major breakthrough. Subsequently, James Maynard and Terence Tao's Polymath project reduced this bound to 246. But the final gap from 246 to 2 remains out of reach.

Goldbach's Conjecture

In 1742, Prussian mathematician Christian Goldbach wrote to Euler proposing: every even number greater than 2 can be expressed as the sum of two primes. Examples: 4=2+2, 6=3+3, 8=3+5, 10=3+7=5+5, 100=3+97=11+89=17+83=29+71=41+59=47+53.

This is one of the oldest unsolved conjectures in mathematics. Computer verification has confirmed it for all even numbers up to 4 × 10¹⁸, but a rigorous proof remains elusive.

7. Primality Testing

Primality testing (determining whether a number is prime) is closely related to prime factorization but fundamentally different: deciding whether a number is prime is much easier than finding its factors.

Miller-Rabin Test

Inventors: Gary L. Miller (1976, deterministic version assuming the Generalized Riemann Hypothesis) and Michael O. Rabin (1980, probabilistic version).

Principle: Based on the contrapositive of Fermat's little theorem. Write n-1 as 2^s × d, pick a random base a, check whether a^d mod n equals 1 or -1, and whether -1 appears in the sequence a^2d, a^4d, ...

Advantage: Each round has error probability at most 1/4. After k rounds, error probability ≤ 4^-k. With 20 rounds, error probability is ~10^-12, reliable enough for practical use. Time complexity: O(k × log² n × log log n).

Usage: The standard method for finding large primes in RSA key generation. Used in OpenSSL, GnuPG, and other cryptographic libraries.

AKS Primality Test

Inventors: Manindra Agrawal, Neeraj Kayal, Nitin Saxena, 2002 (IIT Kanpur, India).

Principle: Based on a generalized Fermat's little theorem: n is prime if and only if the polynomial identity (x + a)ⁿ ≡ xⁿ + a (mod n) holds. AKS cleverly reduces this condition — which naively requires checking exponentially many polynomial coefficients — to a form verifiable in polynomial time.

Complexity: O(log⁶ n) (original), improved to O(log³ n) under certain conjectures.

Practical use: Although theoretically groundbreaking, AKS is much slower than Miller-Rabin in practice, so cryptographic implementations still prefer Miller-Rabin. The value of AKS lies in its theoretical significance — it establishes the exact position of primality testing in computational complexity theory.

Primality Testing Comparison

*Miller-Rabin's deterministic variant requires the Generalized Riemann Hypothesis.

8. Related Tools

• GCD/LCM Calculator — Compute greatest common divisor and least common multiple with step-by-step Euclidean algorithm.
• Modular Arithmetic Calculator — Modular addition, multiplication, and exponentiation — core operations in RSA encryption.
• Combinations & Permutations Calculator — Compute permutations and combinations, the combinatorial foundation behind the divisor count formula.

9. FAQ