二次篩選法

二次篩選。但對於大約 100 位數以內的整數，它仍然是最快的演算法，而且比起普通數域篩選法來說簡潔得多。這是一個通用的整數分解演演算法，意即其運算時間完全取決於欲分解的整數本身位數的大小，而不是在於特殊結構或特性。二次篩選法是由卡爾·帕梅朗斯在1981年所發明，並作為理查德·施羅佩爾的線性篩法之改良版。基礎目標.此演演算法試圖去建立一個模 formula_1 下的平方同餘，這往往即是formula_1的因數分解。演演算法有兩個階段：「資料收集」，在此階段收集可能可以找到一個平方同餘的資料；以及「資料處理」，它把所有收集的資料放進一個矩陣裡，並解決、獲得一個平方同餘數。資料收集的階段可以很輕易地使用多個處理器去平行化。但資料處理階段需要大量的記憶體，並且在多個運算節點之間有效地平行化相當困難，也可能每個運算節點的記憶體不夠足以儲存整個陣列。而可以使用在一些可以儲存陣列的系統。要找到一個平方同餘，一個較天然的方法便是隨機挑選數字，將其平方，並希望模formula_1之後的非負餘數是一個完全平方數。 例如：formula_5 模 formula_6，同時也是formula_7。這種方法對很大的formula_1值而言，可以找到一個同餘的平方數的情況很罕見。但是當真的找到了一個時，在大多數情況下，同餘數為非平凡解而整數分解便完成了。這大致上即是費馬因式分解法的核心。而二次篩選法改良自。一般來說，二次篩選法的執行時間為formula_10L-符號。上式常數 e 為自然對數之底數。解決方法.令 formula_11 模 formula_12 表示為 formula_11 除以 formula_12 之後所剩的餘數。 為了分解整數 formula_15， 牽涉到需要尋找一個數字 formula_16（formula_17是一個完全平方數。 但這些formula_16值相當難找到。 二次篩選法包括對於好幾個formula_16值去計算了formula_20，然後在formula_16值與formula_20的集合中找到一個子集，當中的元素之乘積為完全平方數。 而產生出一個平方同餘。例如：formula_23 模 formula_24、formula_25 模 formula_26 以及 formula_27 模 formula_28 為 formula_29。 在這些數字。formula_34 的觀察因而給出了一個平方同餘：formula_35 (模 formula_28)。但是，如何將以下問題解決呢？「給予一組數字，找到一個子集使其乘積是平方數。」該解決方案使用了指數向量的概念。而指數向量，例如根據算術基本定理，504 可分解為 formula_37。這表示可以藉由指數向量 formula_38，代表 formula_39 在因式分解的指數值。490 會同樣可分解為指數向量 formula_40。將這些數字相乘相當餘把其指數向量的對應值一一相加：formula_41 得一向量 formula_42。有一些數字為平方數，其滿足每個在其指數向量的各個數字為偶數。 例如，向量 formula_43、formula_44 之和為 formula_45，因此 56 乘以 126 是一個平方數。 找尋一個平方數只需對於向量裡數字之的奇偶性之知識，所以有可能將整個向量簡化為模 2 的形式並作模 2 下的加法: formula_46。 在實作中，這相當地有效率，因其可以表示為一位元集。於是此問題變化為：「給予一個 0, 1向量構成的集合，找到一個子集，其中所有向量之和為模 2 的零向量。」而這是一個線性代數的問題；且該解答為線性相依的。線性相依是線性代數中的一個定理：當有比每個向量中含有的元素還要多的向量時，這種相依關係必然存在。而它可以被高效率地找到，例如：把所有向量一列一列地排在一個矩陣裡 ，然後使用高斯消去法。比起實數來說，此方法尤其容易套用到模 2 後的整數上。而此演演算法所需的平方數即是那些向量所對應的數字之積。然而，純粹地只去將一堆隨機數字平方並模 formula_1 會產生很大量的、不同的質因數，也因此會產生出很長的向量以及一個非常大的矩陣。解決方法是去找到一些特別的數字 formula_16，使得 formula_49 模 formula_1 之值只由很小的質因陣列成。此種數字很難被找到，但是若僅使用光滑數將可以保持向量和矩陣之尺寸更小、更容易處理。而二次篩選法使用一種之後會提及名為「篩法」的技巧去找尋光滑數，也就是此演演算法的命名由來。演演算法.總地來說，二次篩演算法基本有以下主要的步驟：本文的剩餘部分將解釋這個基本演演算法的細節和延伸。二次篩法如何最佳化找尋同餘.二次篩選法試圖找到一整數對 formula_11 和 formula_83 其滿足比 formula_86模 formula_57 還要弱得多的條件。它選擇一些質數作為一集合作為「"因數基底"」，並試圖找到 formula_11 ，使得 formula_89 模 formula_1 之值的質因數只會在此因數基底。 此時可稱 formula_12 值：對於此因數基底是"光滑的"。formula_83 的其中一個值之因式分解。 二次篩選法藉由採取接近 formula_1 的平方根之 formula_11 值，以加速尋找這類「關係」的過程。 這將確保 formula_83 會較小，因而具有更大的可能性是光滑的。formula_97formula_98這意味著， formula_12 在 formula_100 的數量級上.。然而，這也意味著 formula_12 的增長幅度與 formula_11 乘以 (formula_1的平方根) 成正比。另一個可以增加光滑的可能性是，即是單純地增大因數基底的大小。 然而，比起因數基底的質數數量，至少找到一個光滑的「關係」還是必要許多，其確儲存在一個線性相依。「部分關係」以及迴圈.即使對於某些「關係」來說， formula_83 並非光滑的。但如果兩個 formula_12 剛好是由因數基底以外的相同質數之乘積，也可能可以合併這兩個"部分「關係」" ，以形成一個完整的「關係」。 [注：此形同於因數基底的擴充套件。]例如：如果因數基底為formula_106和 formula_107，存在「部分關係」：formula_108formula_109將上面兩式乘在一起：formula_110並將等號兩邊皆乘上 formula_111 模 formula_112。而 formula_113 對 formula_112 取模為 formula_115，所以：formula_116formula_117即產生了一個完整的「關係」。 這樣的一個完整的「關係」稱為"迴圈"。 有時候，從兩個「部份關係」形成的迴圈，可以直接導向一個平方同餘，但是此情況非常罕見。藉由篩選來檢查光滑度.有好幾種方法可以 formula_12 值們的光滑度。 最直覺的是藉由試除法，儘管這樣會增加資料收集階段的執行時間。另一個方法較能被接受的方法是。而在實作中，稱為"篩選"的方法比較會被經常使用。 設 formula_119 為多項式 formula_120 我們得：formula_120formula_122formula_123formula_124因此解決出 formula_125模 formula_126對於某個 formula_11 值，將產生出一整個序列，當中的每個數值 formula_128 皆可被 formula_129 整除。 此問題便是對某個質數取模下找到一個平方根，對其存在著高效率的演演算法，例如的。篩選一開始將一個大陣列 formula_132 每個「元」的每個位元組設為零。 對於每一個 formula_129 ，去解決模formula_129 下的二次方程式並得到兩個根 formula_135 和 formula_136，然後在每個 formula_137 模 formula_129「元」之中加入一個近似於 formula_139 之值……也就是 formula_140 和 formula_141。 為了辨識數字是否可被因數基底中的質數之平方所整除，解決幾個模 ( formula_129 的小次方) 下的二次方程式也是必要的。在因數基底的尾端，任何 formula_132 有包含一個值超過大約為 formula_144 的臨界值，將會對應到一個 formula_83 值，其由因數基底的部分組成。 那些包含了確定 formula_83 可以被哪些質數整除的資訊已經遺失掉了，但是因為其只包含一些小的因數，而且已知有很多優良的演演算法可以去分解那些已知只有小因數的數字。例如小質數的試除法、SQUFOF、波拉德 ρ，以及ECM，以上是經常作為一起使用的方法。基本上很多 formula_83 值都會是可行的，因此因式分解過程的尾聲不需要是完全可信的；通常此過程大約有 5% 的輸入會出現異常，此時需要做少量的額外篩選。基本篩選的例子.以下例子將演示沒有作對數最佳化或是質數次方的標準的二次篩法。 令要分解的數為 formula_148，因此平方根 formula_149 無條件進位為124。 由於 formula_149 很小，因此基本的多項式即足夠了： formula_151。資料收集.因為 formula_149 為小數字，所以只需 4 個質數。 滿足在模 formula_129 下 15347 有一平方根的前 4 個質數 formula_129 為 2、17、23 以及 29(換句話說，對這些質數來說，15347是一個模這些數字的二次剩餘)。 這些質數將是篩選的基礎。現在我們要建造出我們的篩選 formula_155從 formula_156並開始對基底裡每個質數進行篩選，以下選擇篩出 formula_157 的那些 formula_158：formula_159下一步即是去作篩選的動作。 對於我們的質數基底 formula_160中的每一個質數 formula_129 值去解決以下方程式：formula_162找到陣列 formula_163 之中可被 formula_129 所整除的那些「元」。對於 formula_165 解出 formula_166 得到了 formula_167。所以，從 formula_168 開始每次 formula_169，每個「元」可被 2 整除。把那些元除以 2 之後得到：formula_170同理，對於剩下的質數 formula_129 formula_172 方程式formula_173 也解決了。值得注意的是，對於每一個 formula_174，因為有兩個模平方根，因此得到 2 個線性方程式。formula_175每個方程式 formula_176 導致 formula_177 從 formula_178 和之後每一次遞增一個 formula_129 值的那些項次皆可被 formula_129 整除。 把 formula_163 中的 formula_16、formula_183、formula_184、formula_185等等的位置除以 formula_129 , 如此對於每個在基底中的質數可以找到為相異質數的乘積之光滑數。formula_187在 formula_163 之中的值等於一的那些「元」皆對應到一個光滑數。 因為 formula_189, formula_190， formula_191 等於一，因此對應到：矩陣處理.由於根據 formula_192的性質我們已經找到平滑數 formula_193 ，而演演算法接著的剩餘部分等同於狄克森因式分解法中的任何變體。將方程式中的一個子集裡的指數乘積formula_194轉為一個矩陣形式 得到以下方程式：formula_195此方程式可由零空間的概念所給出一個解，為：formula_196因此三個方程式的乘積產生了一個平方數：formula_198以及formula_199所以此演演算法找到了formula_200測試其結果得到 formula_201，為 15347 的一個非平凡因數，而另一個為149。而以上恰好顯示出，二次篩法只適用於 formula_1 值較大時。 對於例如像 15347 這類的小數字，此演演算法顯得過猶不及。 試除法或是波拉德 ρ都可以在少量許多的計算之下找到一個因數。倍數多項式.在實際用途上，有許多相異的多項式用在 formula_12 上，因為僅僅一個多項式通常不足以產生出對於因數基底的光滑數對 formula_204。 使用的多項式使用必須要有一個特別形式，因為它們需要為模 formula_1. 下的平方數。 多項式必定會與原始的 formula_206 有類似的形式：formula_207假設 formula_208 是 formula_209 的一個倍數，則 formula_210 且多項式 formula_83 可以被寫作 formula_212。而如果 formula_209 為一個完全平方數，則只需考慮 formula_214的部分。此方式非常適合平行運算，因為每一個處理因式分解的處理器可以單純的給入 formula_1 、因數基底以及多項式的集合，且直到運算完多項式之前都不須跟中央處理器作任何傳輸。大質數.單一的大質數.如果在除以所有小於 formula_209 的因數之後，剩餘的數字小於 formula_217，那麼這個餘因子必為質數。 實際上，藉由對於餘因子去排序「關係」表，則它可以新增進因數基底裡。如果 formula_218 且 formula_219, 則 formula_220。 此可以降低以上完整執行因式分解的篩選陣列之「元」的臨界值。更多的大質數.甚至更進一步去降低臨界值，並且使用一個高效處理將 formula_83 之值分解為一些更大的質數之積可以找到因數大多在因數基底，但有兩個甚至三個大質數的「關係」。 迴圈的尋找過程因此允許一個共享好幾個質數的「關係」集合，合併成為單一的「關係」。實際例子下的引數.為了展示在一個有包含多個多項式以及大質數最佳化下的實作方式去跑實際例子，會有的典型引數選取， 將一個 267 位元的半質數輸入進 msieve 中，產出了以下的引數：整數分解的紀錄.直到發現普通數體篩選法，但在實際情況中，QS 速度更快，因為它採用的是單精度浮點數操作而不是橢圓曲線所使用的高精度計算。在 1994 年的 4 月，RSA-129 的因數分解藉由 QS 完成了。 其為一個由兩個大質數相乘的129 位數數字一個因數為 64 位長而另一個為 65 位。 此因數分解的因數基底包含了 524339 個質數。 資料收集階段花了 5000 個 MIPS 年，其完成於網際網路上的分散式計算。 資料收集總量為 2 GB。 資料處理花了45個小時在 Bellcore ( 現為 Telcordia 科技公司) 的 MasPar 超級電腦。 這曾是最大的、藉由通用演演算法的公開分解，直至 NFS 被用於分解 RSA-130，於 1996 年 4 月 10 日 完成。 所有自此以後分解的 RSA號碼 皆使用 NFS。目前 QS 的紀錄是 formula_223 的一個 135 位數長之餘因子，其為 formula_224的一個 Aurifeuillian因數 ，在 2001 年分解為 66 位以及 69 位數長的質因數。