使用橢圓曲線進行因式分解的算法的影響問Qmathbb{Q}

最近出現了一些論文，描述了一種新的分解方法，使用橢圓曲線 $ \mathbb{Q} $ . 見，例如，

• 整數分解和計算橢圓曲線有理點，Iftikhar A. Burhanuddin 和 Ming-Deh A. Huang。
• Factoring integers using elliptic curves over Q , Xiumei Li, Jinxiang Zeng, arXiv:1207.0274v2.

然而，這些論文似乎並沒有描述這些新方法的複雜性。這些方法的執行時間是多少？這些方法是否比已知的標準分解算法更快？這些新想法對 RSA 和其他基於因子的密碼系統的安全性有何影響？我們應該擔心嗎？

我不認為這裡有什麼可擔心的。第二篇論文中的備註 4.2 和 4.3 指出，這些方法首先需要在具有非常大的導體/判別式的曲線上找到一個點，這似乎非常困難。（比使用 NFS 分解整數更難。）

有許多方法可以計算因式分解和離散對數，您首先進行一些非常困難的數論計算（例如，與有理數上的橢圓曲線相關），然後輕鬆分解或計算 d.log。我自己設計過一次這樣的算法，完全沒用。

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