Factoring
破解 RSA 的最快整數分解是什麼？
我在 Wikipedia 上讀到，破解 RSA 的最快算法是 GNFS。
在一篇 IEEE 論文（MVFactor：一種減少因式分解算法處理時間的方法）中，我讀到最快的算法是 TDM、FFM 和 VFactor。
其中哪一個實際上是正確的？
IEEE 的論文很愚蠢。
他們給出的分解方法很慢，除了極少數情況。例如，在他們的表 1 中，他們自豪地展示了他們改進的算法需要 653.14 秒來分解 67 位數字；好吧，我只是用更傳統的算法試了一下，花了 6 毫秒；是的，速度是原來的 100,000 倍……
其中哪一個實際上是正確的？
**兩個都。**從閱讀摘要看來，論文並沒有聲稱“VFactor”或費馬分解（“FFM”）或試除法（“TDM”）是一般最好的方法。但是，如果素數之間的差 $ p,q $ 和 $ n=pq $ 真的很小，喜歡 $ \ll2^{100} $ $ ;\dagger $ ，那麼 FFM（可能還有 VFactor 變體）會快很多。
雖然通常兩個相同長度的隨機素數之間的差異約為 $ \sqrt{n}/2 $ 這是關於 $ 2^{1024} $ 對於實際大小的模數，因此這些攻擊在那裡不起作用。即使使用 400 位模數，使用使用 GNFS 的家庭桌面很容易破解，但這種差異仍然約為 $ 2^{200} $ 因此太大了。
當然，密鑰生成的實現可能是錯誤的，並且在太小的間隔內發出素數，而在這些情況下，這些專門的算法真正發揮作用。
$ \dagger $ ：“ $ \ll $ “這裡的意思是“少很多”