FACTOR BASE

In computational number theory, the 'factor base' is a mathematical tool commonly used in, as its name suggests, integer factorization algorithms, more specifically algorithms involving extensive sieving of potential factors.

Contents

Usage

Usage

The factor base is a relatively small set of prime numbers ''P''. Say we want to factorize an integer ''n''. We generate, in some way, a large number of integer pairs (''x'', ''y'') for which $x$
eq y and $extstyle\; x\; equiv\; y\; pmod\{n\}$, and ''x'', ''y'' can be completely factorized over the chosen factor base — that is, they are ''p''-smooth for the largest prime ''p'' in ''P''.
We find a subset ''S'' of the integer pairs such that $extstyle\; prod\_\{\}\; x\; hbox\{,\; \}\; (x\; hbox\{\; in\; \}\; S)$ and $extstyle\; prod\_\{\}\; y\; hbox\{,\; \}\; (y\; hbox\{\; in\; \}\; S)$ are both perfect squares. Over our factor base this reduces to adding exponents modulo 2, as we can distinguish squares from non-squares simply by checking the parity of the exponents. Once such a subset is found, we have essentially found a congruence of squares modulo ''n'' and can attempt to factorize ''n''. This congruence may generate the trivial $extstyle\; n\; =\; 1\; cdot\; n$; in this case we try to find another suitable subset. If no such subset is found, we can search for more (''x'', ''y'') pairs, or try again using a different factor base.
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.