Encyclopedia

Factor base

Small set of prime numbers used in sieving algorithms

Wikipedia contributorsAdapted for Fathomly · View authors

1 min read
Source updated August 28, 2025

In computational number theory, a factor base is a small set of prime numbers commonly used as a mathematical tool in algorithms involving extensive sieving for potential factors of a given integer.

01Usage in factoring algorithms

A factor base is a relatively small set of distinct prime numbers P, sometimes together with −1. Suppose we want to factorize an integer n. We generate, in some way, a large number of integer pairs (x, y) for which $x\neq \pm y$ , $x^{2}\equiv y^{2}{\pmod {n}}$ , and $x^{2}{\pmod {n}}{\text{ and }}y^{2}{\pmod {n}}$ can be completely factorized over the chosen factor base, that is, all their prime factors are in P.

In practice, several integers x are found such that $x^{2}{\pmod {n}}$ has all of its prime factors in the pre-chosen factor base. We represent each $x^{2}{\pmod {n}}$ expression as a vector of a matrix with integer entries being the exponents of factors in the factor base. Linear combinations of the rows corresponds to multiplication of these expressions. A linear dependence relation mod 2 among the rows leads to a desired congruence $x^{2}\equiv y^{2}{\pmod {n}}$ . This essentially reformulates the problem into a system of linear equations, which can be solved using numerous methods such as Gaussian elimination; in practice advanced methods like the block Lanczos algorithm are used, that take advantage of certain properties of the system.

This congruence may generate the trivial $\textstyle n=1\cdot n$ ; in this case we try to find another suitable congruence. If repeated attempts to factor fail we can try again using a different factor base.

02Algorithms

Factor bases are used in, for example, Dixon's factorization, the quadratic sieve, and the number field sieve. The difference between these algorithms is essentially the methods used to generate (x, y) candidates. Factor bases are also used in the Index calculus algorithm for computing discrete logarithms.

Watch videos about Factor baseExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Factor base”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.