Prime factorization calculator

A whole number (up to 300 digits), or a form like 2^64+1

 Factor it

36017296008514751432^64 + 12^67 − 12^128 + 1 (too hard)RSA-100 (too hard)

Nothing you type here leaves your browser. The page stops after six seconds on numbers that are too hard.

This prime factorizer splits any whole number into its primes, and it shows the number of divisors, their sum, Euler's phi and a factor tree along the way. Type a number or an expression like 2^64+1 and it runs in your browser. Numbers with a few dozen digits are instant, and the page says plainly when one is too hard.

Using it

Type a whole number, or an expression such as 2^64+1 or 20!+1, and press Factor it. You get the prime factorization, the number of divisors, their sum, Euler's phi, a factor tree you can read at a glance and, for numbers with at most 200 divisors, the full list. For a prime, the page says so. For a number that's too hard, it stops after six seconds and tells you what it found. The address updates to ?n= with your number so a result can be shared, and nothing else leaves your browser.

What it does

Every whole number above 1 is a product of primes in exactly one way, apart from the order. 360 is 2³ × 3² × 5, and no other set of primes multiplies to 360. The tool finds that product in three stages. It divides by the small primes first, which settles most numbers at once. Then it asks whether what's left is already prime, using the Miller–Rabin test. If not, it hunts for a factor with Pollard's rho method, in Richard Brent's faster version, and repeats until nothing composite is left.

Pollard's rho is a clever way of finding a collision. Pick a function such as x → x² + c and iterate it modulo n. Modulo an unknown prime factor p of n, the sequence has to repeat after about the square root of p steps (the birthday paradox). When it does, the difference of two terms shares the factor p with n, and a gcd reveals it. The whole thing runs without ever knowing p. That makes the work about the square root of the smallest factor, which is quick for 10 digits and hopeless for 40.

A few worked numbers

These come from scripts/examples/maths-tools-examples.mjs, which runs the same code. 600,851,475,143, the number from Project Euler's third problem, is 71 × 839 × 1,471 × 6,857, and the tool finds it in a millisecond. 2⁶⁴ + 1 is 274,177 × 67,280,421,310,721, the factorization of the sixth Fermat number that Fortuné Landry found in 1880. 2⁶⁷ − 1, which Mersenne claimed was prime, is 193,707,721 × 761,838,257,287. Frank Nelson Cole showed this to the American Mathematical Society in 1903 by working out the multiplication on a blackboard without saying a word, and the audience applauded. 10³⁰ + 57 is prime, so there's nothing to factor.

The seventh Fermat number, 2¹²⁸ + 1, is one the tool can't do. It has 39 digits, and its smaller factor has 17 (5,704,689,200,685,129,054,721 × 59,649,589,127,497,217). The page gives up after six seconds, because Pollard's rho would need roughly 250 million steps for the 17-digit factor. Michael Morrison and John Brillhart first found the factorization in 1970, with a different method, the continued-fraction algorithm.

Why factoring matters

This is the problem RSA rests on. Multiplying two 1,024-bit primes takes a microsecond, and recovering them from the product with the best methods known today takes an infeasible amount of work. The button marked RSA-100 loads a 100-digit number that's the product of two 50-digit primes. RSA Laboratories published it as a challenge, and it fell in 1991 to a team led by Arjen Lenstra. This page can't do it and gives up after six seconds. The record for a challenge number of this kind is RSA-250 (829 bits, 250 digits), factored in February 2020 with about 2,700 core-years of computing. Keys of 2,048 bits are far beyond any of that. The RSA toy lets you break small keys with the same idea, and the RSA key-size page shows how the primes are chosen.

It's also why a quantum computer would matter. Shor's algorithm factors in polynomial time, which is one reason for the post-quantum ciphers. None of this touches cipher.ink's own messages, which use AES and PBKDF2, with no factoring problem inside.

Common questions