分解算法是否可並行化？

我正在閱讀有關 Blum-Blum-Shub 隨機數生成器的資訊，它的安全性取決於分解非常大的數字的難度（就像加密中的許多事情一樣）。

我只是想知道，如果我有 10 台電腦，我能否將 Blum-Blum-Shub 的破解速度提高 10 倍？還是不可能使用並行計算更快地分解數字？

很不幸的是，不行！與 DLP（離散對數問題）相比，分解是建構許多密碼系統或密碼協議的難題，被稱為 IFP 問題。

即使在這種情況下 $ M= 10^{10} $ 電腦可用，您無法將 IFP 的解析度提高 M，除非您發明了一種新的聰明的算法（高度可並行化）。嘗試蠻力攻擊，即使在 512 位的適度模數長度上也是超出範圍的，並且將花費數十億年。今天為完成這項任務而聞名的最佳算法（它在幾個月內成功地在大型電腦網路上分解到 768 位）是 Number Field sieve 或簡稱 NFS。粗略地說，它基於兩個主要步驟，並且需要大量的記憶體儲存。

• 篩分步驟：可以在大型電腦網路上並行執行。但不幸的是需要大量的記憶體儲存，
• 歸約步驟：線性代數歸約作為高斯消元或細化作為 Bloc Lanczos 歸約，需要求解一個巨大的矩陣且不能並行化。

注意：我得出結論，分解算法是密碼學的核心和重要問題。不要忽視它！瀏覽一下在這個領域所做的工作的網路，以衡量這類問題的重要性。

引用自：https://crypto.stackexchange.com/questions/24551