因數基底

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

在整數分解演算法的應用

因數基底是一個相對小、由相異質數構成的集合 P , 有時會包含著 -1[1]。 假設我們想要因數分解一個整數 n 。 我們利用某些方式生成了數量很多的整數對 (x, y) ,其中     可以完全被因數基底裡的元素分割——也就是說,它們的質因數全部都在 P 裡。

實際上,好幾個滿足   的整數 x 之質因數全部都在預先選定的因數基底裡。 我們將每個   的表達式表示成一個矩陣中的向量,其中的每個整數「元」(entries)為因數基底裡的因數之次方。 矩陣中的列之線性組合對應到這些表達式的乘法。 一個模 2 下矩陣列的線性相依將導向所需的同餘關係  [2]。 這基本上將問題轉化成為了一個線性方程組,其可以藉由許多的方法求解,例如:高斯消去法;實際上,更進階的方法像是block Lanczos演算法會被使用,其利用了此方程組的一些特殊性質。

這類同餘關係可能會產生平凡解: ;在這樣的狀況下我們需要試圖找到其他適合的同餘關係。如果重複嘗試後依然分解失敗,則我們可以改用另一個因數基底再試一次。

演算法

因數基底被用於,例如:狄克森因式分解法二次篩選法以及普通數域篩選法。 這些演算法基本差別在於生成 (x, y) 數對的方法之上。 因數基底也可用在索引運算演算法其用於計算離散對數[3]

參考文獻

  1. ^ Koblitz, Neal, A Course in Number Theory and Cryptography, Springer-Verlag: 133, 1987, ISBN 0-387-96576-9 
  2. ^ Trappe, Wade; Washington, Lawrence C., Introduction to Cryptography with Coding Theory 2nd, Prentice-Hall: 185, 2006, ISBN 978-0-13-186239-5 
  3. ^ Stinson, Douglas R., Cryptography / Theory and Practice, CRC Press: 171, 1995, ISBN 0-8493-8521-0