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.
Usage in factoring algorithms
A factor base is a relatively small set of distinct prime numbersP, sometimes together with -1.[1] Say we want to factorize an integer n. We generate, in some way, a large number of integer pairs (x, y) for which , , and 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 has all of its prime factors in the pre-chosen factor base. We represent each 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 .[2] 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 ; 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.