Prime Factorization Calculator

About Prime Factorization Calculator

This tool factors integers from 2 up to 2¹²⁸ − 1, about 3.4 × 10³⁸ or 39 digits. It works in three stages. Trial division by the small primes up to 2²⁰ (about a million) strips off small factors; a Miller–Rabin test checks whether what is left is prime; and if it is composite, Brent's version of Pollard's rho algorithm finds a factor, after which each piece is factored in turn.

The 39-digit limit comes from 128-bit integer arithmetic written directly in WebAssembly. Ordinary JavaScript numbers stop representing integers exactly above 2⁵³, about 9 × 10¹⁵. How long a result takes depends less on the size of the number than on the size of its second-largest prime factor, so two 39-digit inputs can finish in a millisecond or in hours.

Why trial division stalls on big numbers

The obvious method is to divide by 2, 3, 5, 7 and so on. A composite n always has a factor no larger than √n, so you can stop there. The trouble is that √n is enormous: for a 20-digit number it is a 10-digit number, so the worst case needs close to ten billion divisions, and for 39 digits it is more than 10¹⁹.

That is why this tool uses trial division only up to 2²⁰. Most integers have several small factors and are almost completely broken down by that stage. What survives is either a large prime or a product of two or three large primes, which is where the cleverer algorithm takes over.

Pollard's rho: finding a factor p in about √p steps

John Pollard's 1975 algorithm iterates a pseudorandom sequence such as x → x² + c (mod n). Reduced modulo an unknown prime factor p, that sequence must eventually repeat, and by the same reasoning as the birthday paradox it tends to repeat within about √p steps. When it does, the greatest common divisor of the difference of two terms and n reveals p. Richard Brent sped up the cycle detection in 1980, and the same year the method split the 78-digit Fermat number F₈.

The key point is that the running time depends on p, the smallest prime factor, not on n. The worst case is a balanced semiprime, two primes of similar size, where p ≈ √n and the number of steps is about n^(1/4). The time estimate the tool shows before a long job assumes that worst case, so a number with even one small factor finishes much sooner than predicted.

Measured on a desktop, the product of two 10-digit primes (20 digits) took about 0.05 seconds and the product of two 13-digit primes (25 digits) about 1.5 seconds. Each extra 16 bits, roughly five digits, multiplies the time by 16, so a 39-digit product of two 20-digit primes can take hours. A 39-digit prime such as 2¹²⁷ − 1, on the other hand, needs only a primality test and returns in about 0.01 seconds.

Testing primality is far easier than factoring

Deciding whether a number is prime and finding its factors are problems of very different difficulty. The Miller–Rabin test exposes composites using a handful of modular exponentiations and never needs to find a factor. Below 2⁶⁴ this tool uses the prime bases 2 through 37, which makes the answer deterministic; above that it uses 18 bases up to 61, a probabilistic test for which no counterexample in this range is known.

A plain Fermat test is fooled by Carmichael numbers such as 561 = 3 × 11 × 17, which pass it for every base coprime to them. Miller–Rabin is not fooled, and entering 561 here immediately returns 3 × 11 × 17.

How RSA depends on factoring being hard

An RSA public key publishes n = p × q for two large secret primes. Anyone can encrypt with n, but building the private key requires p and q. Multiplying is instant and undoing it is not; that asymmetry is the whole basis of the scheme. RSA-129, a 129-digit number published in Martin Gardner's Scientific American column in 1977, was factored only in 1994, by a project that pooled volunteers' computers around the world.

RSA keys in use today are typically 2048 bits, about 617 digits, sixteen times the bit length this tool accepts. Numbers that size call for the number field sieve rather than Pollard's rho, and even so the public factoring records are far below 2048 bits. Factoring a 64-bit and then an 80-bit semiprime here is a quick way to feel how fast the cost grows with each added bit.

Worked examples

How to use it

1. Enter an integer of 2 or more; commas and spaces are ignored.
2. For large inputs an estimated worst-case time appears first, and you can stop the calculation at any point.
3. Repeated factors are grouped with exponents; tap a history entry to copy the equation.

Frequently asked questions