text: 在計算數論裡， 因數基底是一個質數所構成的小集合。經常作為數學工具用於演演算法裡，包含給定一個數字去廣泛地篩出可能的因數。在整數分解演演算法的應用.因數基底是一個相對小、由相異質數構成的集合 "P" ， 有時會包含著 -1。 假設我們想要因數分解一個整數 "n" 。 我們利用某些方式生成了數量很多的整數對 ("x", "y") ，其中 formula_1、 formula_2 且 formula_3 可以完全被因數基底裡的元素分割——也就是說，它們的質因數全部都在 "P" 裡。實際上，好幾個滿足 formula_4 的整數 "x" 之質因數全部都在預先選定的因數基底裡。 我們將每個 formula_4 的表示式表示成一個矩陣中的向量，其中的每個整數「元」為因數基底裡的因數之次方。 矩陣中的列之線性組合對應到這些表示式的乘法。 一個模 2 下矩陣列的線性相依將導向所需的同餘關係 formula_6。 這基本上將問題轉化成為了一個線性方程組，其可以藉由許多的方法求解，例如：高斯消去法；實際上，更進階的方法像是block Lanczos演演算法會被使用，其利用了此方程組的一些特殊性質。這類同餘關係可能會產生平凡解：formula_7；在這樣的狀況下我們需要試圖找到其他適合的同餘關係。如果重複嘗試後依然分解失敗，則我們可以改用另一個因數基底再試一次。演演算法.因數基底被用於，例如：狄克森因式分解法、二次篩選法以及普通數域篩選法。 這些演演算法基本差別在於生成 ("x", "y") 數對的方法之上。 因數基底也可用在索引運算演演算法其用於計算離散對數。
metadata: erhwenkuo/wikipedia-zhtw
metadata: 因數基底
metadata: https://zh.wikipedia.org/wiki?curid=6522318