因数基底

在计算数论里， 因数基底是一个质数所构成的小集合。经常作为数学工具用于演算法里，包含给定一个数字去广泛地筛出可能的因数。

在整数分解演算法的应用

因数基底是一个相对小、由相异质数构成的集合 P ， 有时会包含著 -1。 假设我们想要因数分解一个整数 n 。 我们利用某些方式生成了数量很多的整数对 (x, y) ，其中 $x\neq \pm y$、 $x^{2}\equiv y^{2}{\pmod {n}}$ 且 $x^{2}{\pmod {n}}{\text{ and }}y^{2}{\pmod {n}}$ 可以完全被因数基底里的元素分割——也就是说，它们的质因数全部都在 P 里。

实际上，好几个满足 $x^{2}{\pmod {n}}$ 的整数 x 之质因数全部都在预先选定的因数基底里。 我们将每个 $x^{2}{\pmod {n}}$ 的表达式表示成一个矩阵中的向量，其中的每个整数“元”（entries）为因数基底里的因数之次方。 矩阵中的列之线性组合对应到这些表达式的乘法。 一个模 2 下矩阵列的线性相依将导向所需的同馀关系 $x^{2}\equiv y^{2}{\pmod {n}}$。 这基本上将问题转化成为了一个线性方程组，其可以借由许多的方法求解，例如：高斯消去法；实际上，更进阶的方法像是block Lanczos演算法会被使用，其利用了此方程组的一些特殊性质。

这类同馀关系可能会产生平凡解：$\textstyle n=1\cdot n$；在这样的状况下我们需要试图找到其他适合的同馀关系。如果重复尝试后依然分解失败，则我们可以改用另一个因数基底再试一次。

演算法

因数基底被用于，例如：狄克森因式分解法、二次筛选法以及普通数域筛选法。 这些演算法基本差别在于生成 (x, y) 数对的方法之上。 因数基底也可用在索引运算演算法其用于计算离散对数。