Integer & prime factorizer

What you can type. Whole numbers of up to 40 digits, with or without separators: 1 000 000, 1_000_000 and 1,000,000 all work. A negative number −n is factored as −1 × n, and 0 and 1 are explained rather than factored.

How it works. Trial division by every prime below 65,536 comes first. What is left goes to Pollard’s rho method in Brent’s variant, after quick checks for perfect powers and for two factors close to √n. All arithmetic is exact, with BigInt.

Prime or probable prime? Below 3.3 × 10²⁴, Miller–Rabin with the first 13 primes as bases is a proof, so the answer is exact. Larger factors are checked with the Baillie–PSW test: no composite number is known to pass it, but it is not a proof, so such factors are marked †.

When it takes too long. Rho needs about √p steps to find a prime factor p, so a 40-digit number made of two 20-digit primes could take hours. The search stops after 10 seconds and shows which factor is left; you can then let it search longer.

Carmichael numbers. 561 = 3 × 11 × 17 passes Fermat’s test aⁿ⁻¹ ≡ 1 (mod n) for every base a coprime to it, just as a prime would. Miller–Rabin also looks at the square roots of 1 along the way, and that exposes it.

Keyboard. Enter factors the number and Esc cancels a long search. The examples fill in the field and factor the number at once.