查看“︁因數基底”︁的源代码

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

== 在整數分解演算法的應用 ==
因數基底是一個相對小、由相異[[質數]]構成的[[集合 (数学)|集合]] ''P'' ， 有時會包含著 -1<ref>{{Citation|first=Neal|last=Koblitz|title=A Course in Number Theory and Cryptography|year=1987|publisher=Springer-Verlag|isbn=0-387-96576-9|page=133}}</ref>。 假設我們想要因數分解一個整數 ''n'' 。 我們利用某些方式生成了數量很多的整數對 (''x'', ''y'') ，其中 <math>x \neq \pm y</math>、 <math> x^2 \equiv y^2 \pmod{n}</math> 且  <math>x^2 \pmod{n} \text{ and }y^2 \pmod{n}</math> 可以完全被因數基底裡的元素分割——也就是說，它們的質因數全部都在 ''P''  裡。

實際上，好幾個滿足 <math>x^2 \pmod{n}</math> 的整數 ''x'' 之質因數全部都在預先選定的因數基底裡。 我們將每個 <math>x^2 \pmod{n}</math> 的表達式表示成一個[[矩陣]]中的[[向量]]，其中的每個整數「元」（entries）為因數基底裡的因數之次方。 矩陣中的列之線性組合對應到這些表達式的乘法。 一個模 2 下矩陣列的線性相依將導向所需的[[同餘]]關係 <math>x^2 \equiv y^2 \pmod{n}</math><ref>{{Citation|first=Wade|last=Trappe|first2=Lawrence C.|last2=Washington|title=Introduction to Cryptography with Coding Theory|edition=2nd|year=2006|publisher=Prentice-Hall|isbn=978-0-13-186239-5|page=185}}</ref>。 這基本上將問題轉化成為了一個[[线性方程组|線性方程組]]，其可以藉由許多的方法求解，例如：[[高斯消去法]]；實際上，更進階的方法像是[[Block Lanczos algorithm for nullspace of a matrix over a finite field|block Lanczos演算法]]會被使用，其利用了此方程組的一些特殊性質。

這類同餘關係可能會產生平凡解：<math>\textstyle n = 1 \cdot n</math>；在這樣的狀況下我們需要試圖找到其他適合的同餘關係。如果重複嘗試後依然分解失敗，則我們可以改用另一個因數基底再試一次。

== 演算法 ==
因數基底被用於，例如：[[Dixon's factorization method|狄克森因式分解法]]、[[二次篩選法]]以及[[普通数域筛选法|普通數域篩選法]]。 這些演算法基本差別在於生成 (''x'', ''y'') 數對的方法之上。 因數基底也可用在[[Index calculus algorithm|索引運算演算法]]其用於計算[[離散對數]]<ref>{{Citation|first=Douglas R.|last=Stinson|title=Cryptography / Theory and Practice|year=1995|publisher=CRC Press|isbn=0-8493-8521-0|page=171}}</ref>。

== 參考文獻 ==
<references group="" responsive=""></references>
[[Category:整数分解算法]]
[[Category:有未审阅翻译的页面]]