哪些算法用於分解大整數？
即使 RSA 決定取消Factoring Challenge，似乎有些團隊還在繼續努力。根據維基百科，RSA-768已在 2009 年底被考慮在內。
目前有哪些大整數分解算法，它們背後的數學原理是什麼？改進的方法是什麼（更快的算法，更好的實現……）？
三種主要的因式分解通用算法是二次篩（QS）、橢圓曲線法（ECM）和數域篩（NFS）。
關於復雜性
這些算法的執行時間用L 表示法表示： $ L_n[a,c] $ 意味著因數分解的漸近複雜度 $ n $ 是 $ O(e^{(c+o(1))(\log n)^a(\log \log n)})^{1-a} $ . 我們承認“ $ \log n $ “作為"數字的大小 $ n $ “所以要查看的主要參數是” $ a $ “，但是，對於給定的” $ a $ “, " $ c $ " 不容忽視。此外，這是一個漸近複雜性，當 $ n $ 是“足夠大”，不知道每天是否“ $ n $ " 值（例如 RSA 密鑰）對於表達式來說“足夠大”，可以精確估計實際分解工作。最後但並非最不重要的是，執行時間僅與 CPU 消耗有關，它不包括記憶體使用，而記憶體是1024 位整數的瓶頸。
二次篩
QS 的描述可以在應用密碼學手冊的第 3 章中找到。在“數論和密碼學課程”中對其進行了更詳盡的詳細介紹，這是一本強烈推薦給對此類主題感興趣的人的書（與手冊相反，這本書不是免費的，但物有所值）。
QS的主要思想是嘗試找到兩個整數，它們是相同值的平方根模 $ n $ . 如果我們考慮 $ n = pq $ （和 $ p $ 和 $ q $ 大素數），然後是大多數具有平方根模的整數 $ n $ 實際上有四個平方根；這可以從中國剩餘定理(CRT) 中看出，它粗略地指出，當你計算模數時 $ n $ ，你實際上是在計算模數 $ p $ 和模 $ q $ 同時。如果 $ z $ 是二次餘數模 $ n $ （它是某個整數模的平方 $ n $ ）， 然後 $ z $ 也是二次餘數模 $ p $ 和模 $ q $ . 模組 $ p $ , $ z $ 有兩個平方根（如果 $ u $ 是平方根 $ z $ , 那麼也是 $ -u $ ）， 和 $ z $ 也有兩個平方根模 $ q $ ，通過 CRT 產生四種可能的組合。的四個平方根 $ z $ 是 $ u $ , $ -u $ , $ v $ 和 $ -v $ 對於兩個值 $ u $ 和 $ v $ .
所以如果我們發現 $ x $ 和 $ y $ 這樣 $ x^2 = y^2 \mod n $ ， 然後 $ x $ 和 $ y $ 是模數相同的兩個平方根 $ n $ . 糟糕的情況是 $ x = ±y \mod n $ ，因為這不會產生任何資訊：這是當 $ x $ 和 $ y $ 是 $ u $ 和 $ -u $ ， 或者 $ v $ 和 $ -v $ . 但是，有 1/2 的機率 $ x $ 和 $ y $ 是 $ ±u $ 和 $ ±v $ ， 分別。那時，一個簡單的GCD之間 $ n $ 和 $ x+y $ 將產生 $ p $ 或者 $ q $ .
在 QS 中，我們設置了兩個界限 $ A $ 和 $ B $ ，我們尋找 $ B $ - 一組中的數字 $ S $ 整數。一種 $ B $ -number 是一個數字，它是 $ B $ -smooth，即它的所有主要除數都小於 $ B $ . 套裝 $ S $ 包含在整數中 $ t^2-n $ , 對於 $ t $ 介於 $ \sqrt{n} $ 和 $ \sqrt{n}+A $ . 所以中的值 $ S $ 是“小”整數，每個都等於平方模 $ n $ 一個“更大”的整數。
假設我們找到了兩個 $ B $ - 平滑整數 $ s_1 $ 和 $ s_2 $ , 這樣 $ s_1 = gh^5 $ 對於一些小素數 $ g $ 和 $ h $ （小於 $ B $ ）， 和 $ s_2 = g^3h^3 $ . 也不是“明顯的正方形”（即純整數中的正方形，不計算模 $ n $ ); 但 $ s_1s_2 = g^4h^8 $ ，這是的平方 $ g^2h^4 $ （純整數中的平方，但這也適用於模 $ n $ ）。然而， $ s_1 $ 和 $ s_2 $ 也是模數的平方 $ n $ 一些中的 $ t_1 $ 和 $ t_2 $ ，分別，所以 $ s_1s_2 $ 是一個正方形 $ t_1t_2 $ 模組 $ n $ . 這產生兩個值 $ x = t_1t_2 $ 和 $ y = g^2h^4 $ 這樣 $ x^2 = y^2 \mod n $ ，正是我們想要的。
QS 的要點是這個過程的概括。我們積累了很多 $ B $ - 平滑值來自 $ S $ ，希望我們能找到這樣的產品 $ B $ - 每個素數除數都有一個偶數指數的平滑值，因為這會產生一個“明顯平方”，我們可以將其等同於從集合的方式獲得的“非明顯平方” $ S $ 被定義。
發現 $ B $ - 集合中的平滑整數 $ S $ 涉及“篩分”，在這種情況下，可以將其視為Eratosthenes 的 Sieve的後代。我們從 $ S $ ，然後我們“標記”所有的倍數 $ r $ 對於每個素數 $ r $ 小於 $ B $ ; 如果其中一個值已經積累了足夠多的標記，那麼它是“許多”小素數的乘積，因此是一個很好的候選者 $ B $ -光滑的。
算法的兩部分因此是篩分的，可以分佈在多台機器上，每台機器都在尋找 $ B $ - 在相對較小的範圍內平滑整數（對於大整數，我們仍在討論在每台機器上使用幾 GB 的 RAM）。那麼，所有 $ B $ - 平滑整數在一個大矩陣中累積：每行 $ B $ -平滑值 $ s $ , 每個素數一列 $ r $ 小於 $ B $ . 排的插槽 $ s $ 和列 $ r $ 如果分解為 1 $ s $ 包括 $ r $ 具有奇數指數；否則，這是一個 0。矩陣縮減步驟試圖找到行的總和（在 $ \mathbb{Z}_2 $ ) 產生一個全零的行（將兩行相加相當於乘以相應的 $ s $ 值，並且全零行意味著該乘積對於所有小素數都有偶數指數，因此是一個明顯的平方）。
篩分將在合理的時間內工作，如果 $ B $ 足夠大（更容易找到 $ B $ -數字，如果你允許更大的“小素數”）。另一方面，矩陣約簡步驟將很有可能找到完整的關係（乘積 $ s $ 值是明顯的正方形）只有當我們發現超過 $ B $ 這樣的 $ B $ -數字；最終矩陣將具有大小 $ B^2 $ ，這可能會變得難以忍受。所以有一個權衡。已經證明（給定一些“合理的”假設）最優選擇導致執行複雜度為 $ L_n[1/2,1] $ .
一種變體稱為多重多項式二次篩，其中 $ S $ 可以接受其他類型的整數，超出 " $ t^2-n $ “格式。請參閱Silverman 的主要論文。
橢圓曲線分解
ECM 分解算法依賴於以下思想：我們計算橢圓曲線上的點，使用取模的值 $ n $ 彷彿 $ n $ 是素數（它不是），熱切地希望事情會在某個時候變壞：我們想要達到一個不可逆模數的值 $ n $ , 因為這樣一個簡單的 GCD 將產生一個非平凡的因素 $ n $ .
橢圓曲線是點的集合 $ (X,Y) $ ， 在哪裡 $ X $ 和 $ Y $ 來自域，使得給定的三次方程成立，通常 $ Y^2 = X^3 + aX + b $ 對於一些常數 $ a $ 和 $ b $ . 在這樣的一組點上，我們可以定義一個群律；這需要一個“中性點”，一個稱為“無限遠點”的額外正常點，它沒有 $ X $ 和 $ Y $ 場中的座標。EC 群定律很容易計算，其公式意味著除法（注意，這是 ECM 的有趣點）：添加點 $ (X_1,Y_1) $ 指向 $ (X_2,Y_2) $ ，我們必須將一些值除以 $ X_2 - X_1 $ . 當我們添加兩個相同的點時 $ X $ 協調但不相同 $ Y $ ，我們得到了無窮大的點（這以某種方式解釋了它的名字：我們“除以零”）。
由於我們可以將點相加，我們可以定義一個點乘以一個整數： $ P $ 經過 $ f $ ，我們反复添加 $ P $ 對自己（ $ f-1 $ 次）。這可以通過雙加算法有效地完成。如果我們使用有限域，則曲線是有限群，這意味著當添加 $ P $ 就其本身而言，我們必然以無窮大點結束。其實任何一點 $ P $ 有一個順序，它是一個整數 $ d $ 這樣 $ fP $ 是無窮遠點 $ f $ 是的倍數 $ d $ .
整數模 $ n $ 不是一個欄位。然而，如果 $ n = pq $ ，那麼，當我們用座標為模的曲線點進行計算時 $ n $ ，我們實際上是同時計算兩條曲線上的點：整數域中的曲線模 $ p $ , 和整數域中的曲線模 $ q $ . 這就是中國剩餘定理的意義所在。所以 ECM 是這樣工作的：
- 我們選擇隨機常數 $ a $ 和 $ b $ 模組 $ n $ ，以及曲線上的一個隨機點。
- 我們反復將該點與整數相乘 $ r^x $ 對於小素數 $ r $ , 和指數 $ x $ , 這樣 $ r^x $ 不大於給定的界限 $ B $ .
- 我們希望在某個時候我們會嘗試做除法模 $ n $ 按值 $ X_2-X_1 $ 這將證明是不可逆的，此時我們將贏得（GCD $ n $ 並且該值將產生一個重要的因素 $ n $ ).
ECM 依賴於希望曲線上的點取模 $ p $ （但不是模 $ q $ ) 會有一個 $ B $ - 流暢的訂單；因此，乘以所有 $ r^x $ 將達到模數 $ p $ （但不是模 $ q $ ) 無窮遠點，即“除以零”。因為我們工作模數 $ n $ ，我們會注意到除以零作為“取模”的情況 $ n $ 不起作用”。
邊界 $ B $ 配置為使我們不會在給定曲線上花費太多時間。如果我們用盡所有小於以下的小素數 $ B $ ，然後我們用另一條曲線（其他隨機 $ a $ 和 $ b $ 常數）。
有一些變體可以提高 ECM 的性能；有關詳細資訊，請參閱此報告。
“平衡”整數（RSA 模數）的執行複雜度 $ n = pq $ 在哪裡 $ p $ 和 $ q $ 大小相同）類似於二次篩。然而，ECM 的複雜性主要取決於最小因子的大小 $ n $ ，而不是大小 $ n $ ，所以這是攻擊大“不平衡”整數（例如，沒有專門生成為 RSA 模數的整數）的首選算法。
數域篩
Number Field Sieve 是一個非常複雜的算法，我不會在這裡詳細說明，因為我很確定我不會做對。作為一種極端的過度簡化，NFS 就像 QS 一樣，到處都是多項式而不是整數。它依賴於大量的數論。但是，它仍然有兩個基本步驟：
- 一個篩分步驟，可以很容易地分佈在許多機器上（每台機器都有大量但並非難以置信的 RAM）；
- 一個矩陣縮減步驟，它不能輕易地分佈在許多機器上，並且涉及對一個巨大的矩陣應用一個理論上簡單的操作（高斯 - 喬丹縮減）。
需要額外的初始化步驟來選擇參數；它通常被稱為“多項式選擇”，需要大量的思考和不可忽略的 CPU 工作。
NFS 在隨機整數上的執行時間（稱為General Number Field Sieve）是 $ L_n[1/3,c] $ 對於一個常數 $ c = (64/9)^{1/3} $ . 對於大於約 350 位的整數，它比 QS 和 ECM 快；所有以RSA-130（430 位）開始直到並包括目前RSA-768（768 位）的分解記錄都使用 GNFS。有一種稱為SNFS（特殊數字欄位篩選）的變體，它僅適用於具有特殊格式的整數（因此不適用於 RSA 密鑰破解），但具有更好的複雜性（ $ L_n[1/3,c] $ 和 $ c = (32/9)^{1/3} $ ，這意味著 SNFS 可以潛在地分解比 GNFS 大兩倍的整數）。SNFS 用於分解一個1024 位整數，該整數是 $ 2^{1039}-1 $ .
對於大整數，因式分解的瓶頸是矩陣縮減步驟，它需要 TB 級的非常快的 RAM，並且不容易分配。有傳言說 1024 位“一般”整數分解的多項式選擇已經開始，但是如果篩選步驟看起來可行（儘管需要幾年時間），那麼沒人知道矩陣縮減步驟將如何執行（即使考慮到五年或十年的技術進步會給我們帶來什麼）。
量子電腦
Shor 的算法很容易分解非常大的整數。它唯一的缺點是它僅適用於（尚不存在）的量子電腦。
論科學進步
我們可能注意到 QS、ECM 和 NFS 都是 1980 年代的算法。在過去的 20 年中，沒有發現任何新的、有效的算法。然而，同時發現了許多優化，導致算法變體（例如 MPQS、具有“第 2 階段”的 ECM ……）比它們最初的描述要快得多，因此已經取得了實質性進展——但是對此的描述進步需要深入了解每個算法的技術細節。
對於超過 115（十進制）數字的數字，目前已知的最佳算法是通用數字域篩選器（GNFS - 有時簡稱為數字域篩選器，儘管還有一個特殊數字域篩選器用於分解特殊形式的數字）。
不幸的是，GNFS 是一個非常複雜的算法，我不知道有任何線上教程可以提供足夠的細節，甚至可以開始實現它（大多數都給出了一個或兩個句子的相當模糊的摘要）。雖然它沒有（甚至接近）足夠自己實現算法，但 GNFS 的 Wikipedia 條目有一些工作實現的連結。
但是請注意，使用 GNFS 分解一個 115 位以上的數字需要大量的 RAM——比大多數人可用的還要多，並且它隨機訪問數據，以至於虛擬記憶體對它毫無用處。
對於稍小的數字，下一個選擇是多重多項式二次篩(MPQS)。這也不是一個簡單的算法，但是Wikipedia 條目（例如）看起來可能足以實現它（並且它還具有指向某些實現的連結）。