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.
Contents
Usage in factoring algorithms
A factor base is a relatively small set of distinct prime numbers P, sometimes together with -1. Say we want to factorize an integer n. We generate, in some way, a large number of integer pairs (x, y) for which
In practice, several integers x are found such that
This congruence may generate the trivial
Algorithms
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.