因數基底

在計算數論裏， 因數基底是一個質數所構成的小集合。經常作為數學工具用於演算法裏，包含給定一個數字去廣泛地篩出可能的因數。

在整數分解演算法的應用

因數基底是一個相對小、由相異質數構成的集合 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) 數對的方法之上。 因數基底也可用在索引運算演算法其用於計算離散對數。