Prime factorization calculator

How it works

Every whole number $n \ge 2$ is a product of primes in exactly one way, up to the order of the factors (the fundamental theorem of arithmetic): $360 = 2^3 \cdot 3^2 \cdot 5$. Finding these primes is easy for small numbers and, as far as anyone knows, extremely hard for large ones.

The calculator first divides by the primes $2, 3, 5, \dots$ up to $10^4$, as long as $p^2$ does not exceed what is left: once no prime up to the square root divides, the rest is prime. Larger parts go through a Miller-Rabin test; a composite part is checked for being a perfect power and then split with Pollard’s rho method. Rho iterates $x \mapsto x^2 + c \bmod m$; modulo an unknown prime factor $p$ this sequence repeats after roughly $\sqrt p$ steps (the birthday paradox), and a gcd with $m$ exposes $p$. That finds factors up to about 12 digits within a few seconds, whatever the size of $n$.

RSA rests on the gap between multiplying and factoring: a 2048-bit modulus $N = pq$ is built in milliseconds, while the best known method (the general number field sieve) is far from factoring it. The largest RSA challenge numbers factored so far have 829 bits.