什麼是最好的素數分解算法及其有效性
我想知道最常用的素數分解算法不是比 RSA 密碼系統的安全性落後一英里嗎？
在我看來，每次算法能夠破解 RSA 或特別是找到兩個素因子時，您只需更改素因子的大小即可。
真的那麼簡單嗎？
無論如何，感謝大家的時間和精力！
真的那麼簡單嗎？
如果不是，我們將不得不放棄 RSA。
原因如下：為了能夠相當快地執行 RSA，它需要在某個參數中以多項式時間執行，我們稱之為 $ \lambda $ . RSA 與模冪運算基本相同，因此可以及時執行 $ \mathcal O(\lambda^3) $ 什麼時候 $ 2^\lambda\approx n $ . 現在最著名的通用分解方法，GNFS 及時執行 $ L_n\left[\frac13,\sqrt[3]{\frac{64}9}\right]=\exp\left(\left(\sqrt[3]{\frac{64}9}+o(1)\right)\cdot\sqrt[3]{\ln{2^\lambda}}\cdot\sqrt[3]{\ln{\ln{2^\lambda}}}^2\right) $ ，它是次指數的 $ \lambda $ . 因此，如果我們將密鑰長度加倍（即 $ \lambda $ )，我們可以將我們的工作量增加 8 倍，但我們也將攻擊者的工作量提升到至少 $ \sqrt[3]2 $ ，這變成了 $ 2^{80} $ 攻擊成 $ >2^{110} $ 攻擊，從而將攻擊複雜性增加至少十億。
現在假設我們可以考慮時間 $ \mathcal O(\lambda^n) $ 對於一些有點小 $ n $ . 現在如果我們將密鑰長度加倍，我們（合法使用者）會花費 8 倍的時間，但攻擊者現在只需要 $ 2^n $ 倍時間，所以如果他有 $ 2^{n-3} $ 多核或多核，他都可以在同一時間恢復新的密鑰。所以我們不得不重複增加密鑰長度幾次（假設 $ n\leq 20 $ ) 這樣我們，使用者，就獲得了攻擊者的優勢，但此時密鑰長度變得如此之大，以至於 RSA 太慢而無法成為一個好的選擇，尤其是在考慮低功耗嵌入式系統時。