因数基底

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

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

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

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