Factoring integers

No factoring algorithm is best for all inputs. The cost of the special purpose methods (trial division, Pollard rho, $p - 1$, $p + 1$ and the elliptic curve method) depends mainly on the size of the factor $p$ they find, while that of the general purpose methods (SQUFOF, the quadratic sieve) depends only on the size of the number $N$ itself. A factoring routine therefore removes small factors first and calls the general methods only on what remains.

The methods#

We write $L_x[\alpha, c] = \exp\bigl((c + o(1)) (\log x)^\alpha (\log \log x)^{1 - \alpha}\bigr)$. The running times below are in arithmetic operations modulo $N$ (or, for the sieve, in operations on small numbers), and those of the randomised methods are heuristic expected values [CraPom2005, Chapters 5–6].

Trial division by all primes up to $b$ finds the factors below $b$. For multiprecision $N$, FLINT divides by the primes one at a time (flint_mpn_factor_trial, a division of $N$ by a word for each prime) or computes $\gcd(N, \prod_{p \le b} p)$ with a product tree of the primes, which is cached (flint_mpn_factor_trial_tree), and then identifies the primes dividing the GCD.

Pollard's rho method [Pol1975] iterates $x \mapsto x^2 + a \bmod N$. Modulo a prime factor $p$ the sequence becomes periodic after about $\sqrt{\pi p/2}$ steps, and a collision $x_i \equiv x_j \pmod p$ is detected as $\gcd(x_i - x_j, N) > 1$. Brent's variant [Bre1980] finds the cycle with powers of two and multiplies the differences together, taking a GCD only every 100 steps.

The $p - 1$ and $p + 1$ methods [Pol1974; Wil1982] compute $a^E \bmod N$ (respectively a Lucas sequence) for $E$ the product of all prime powers up to a bound $B_1$; if $p - 1$ (respectively $p + 1$) divides $E$, then $p$ divides $\gcd(a^E - 1, N)$. A second stage allows one larger prime up to $B_2$. They succeed only for special $p$.

The elliptic curve method [Len1987] replaces the group $(\mathbb{Z}/p\mathbb{Z})^*$ of order $p - 1$ by the group of points of a random elliptic curve modulo $p$, whose order varies in $[p + 1 - 2\sqrt p, p + 1 + 2\sqrt p]$: trying many curves gives many chances of a smooth order. See The elliptic curve method.

SQUFOF [GowWag2008] walks through the continued fraction expansion of $\sqrt{kN}$ looking for a square form, using only arithmetic on numbers of half the size of $N$; it is the method of choice for $N$ of up to about 70 bits.

The quadratic sieve [Pom1985] finds many $x$ for which $x^2 - kN$ factors over a base of small primes, combines them into a congruence of squares $X^2 \equiv Y^2 \pmod N$ by linear algebra over $\mathbb F_2$, and splits $N$ with $\gcd(X - Y, N)$. See The quadratic sieve.

FLINT has no implementation of the number field sieve, whose running time $L_N[1/3, (64/9)^{1/3}]$ makes it faster than the quadratic sieve above about 100 digits.

Words: n_factor#

For $N < 2^{64}$, n_factor removes the primes up to $2^{16}$ by trial division and then splits the remaining cofactor, which has at most three prime factors, with rho, Hart's one-line method and SQUFOF. See Factoring word-size integers. Two-word versions of rho, ECM and SQUFOF (n_ll_factor_rho, n_ll_factor_ecm, n_ll_factor_SQUFOF) are used by fmpz_factor for cofactors of up to 128 bits.

Multiprecision integers: fmpz_factor#

fmpz_factor proceeds as follows (Factoring integers has more details).

1. Remove the powers of 2, then trial divide by the primes from 3 in blocks of 1000 primes, continuing with the next block as long as factors are found. A cofactor of one word is finished with n_factor.
2. Check whether the cofactor is a proven prime (fmpz_is_prime) or a perfect power (fmpz_is_perfect_power); in the latter case factor the root.
3. Run _fmpz_factor_smooth with the bound $\max(b/3 - 17, 2)$ bits for a $b$-bit cofactor: trial division by the first 3512 primes with a product tree, then the elliptic curve method with the parameters of the table below for factors of increasing size (from about 18 bits, in steps of 6 bits), lowering the bound as the cofactor shrinks.
4. Split what remains: on 64-bit machines, for cofactors of at most 128 bits, by two-word rho (2048 or 8192 iterations), from 118 bits a few two-word ECM curves, and up to 72 bits by SQUFOF; otherwise, or if these fail, by the quadratic sieve.
5. Factor the pieces recursively, from step 2.

The choice of the bound $b/3 - 17$ in step 3 reflects the costs: the elliptic curve method finds a factor of $f$ bits in time $L_{2^f}[1/2, \sqrt 2]$, while the sieve takes $L_{2^b}[1/2, 1]$; looking for factors of up to about a third of the size of the number before switching to the sieve is a good compromise, and the constant was tuned on random inputs. The table of elliptic curve parameters (fmpz_factor_smooth, with $B_2 = 100 B_1$) is designed to find a factor of the given size with probability about $1/3$ at each size, so that over the overlapping sizes a factor of $f \le$ the bound bits is found with probability at least about $2/3$:

All prime factors returned by fmpz_factor are proved prime, by the methods of Primality proving: APRCL and ECPP. fmpz_factor_smooth with proved = 0 checks only probable primality, which is much faster for large factors.

@misc{flint-doc-algorithms-number-theory-integer-factoring,
  author       = {{The FLINT team}},
  title        = {{Factoring integers}},
  howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
  year         = {2026},
  url          = {https://flintlib.org/doc/algorithms/number-theory/integer-factoring.html},
  note         = {Generated 2026-11-02}
}