Leandro Junes

Prime Factorization

Factor integers in your browser with adaptive methods, from trial division to ECM and the quadratic sieve.

Inputs

Before you factor Difficulty depends on factor size, not just input size. Factoring runs in your browser; you can stop anytime, and results may be partial.

Any integer, arbitrarily large. Optional leading + or −.

Try

Factorization

—

n = —

—

Status
—
Elapsed
—
Factors found
—

How it works

  1. Trial division removes small prime factors up to a fixed bound.
  2. Perfect-power detection checks whether what's left is exactly a^k, using exact integer roots.
  3. Primality testing classifies the remainder — deterministic below roughly 3.3 × 10²⁴, Baillie–PSW above it.
  4. SQUFOF gets a fast, cheap attempt at moderately sized cofactors.
  5. Pollard–Brent rho looks for a small-to-medium factor.
  6. Pollard p−1 and Williams p+1 look for a factor p where p∓1 is smooth.
  7. The elliptic curve method (ECM) tries increasingly many curves at increasing bounds — effective when a composite has a relatively small factor.
  8. The self-initializing quadratic sieve (SIQS) handles composites in its size range once ECM hasn't found anything; it suits balanced semiprimes, where ECM has no small factor to find.
  9. Any factor found is split off and the same pipeline runs again on both pieces.

Methods are chosen automatically. Difficult composites may stay unresolved — Continue factoring resumes with a stronger schedule. Very balanced semiprimes well past this calculator's tested range may remain unresolved regardless.