Discrete-Logarithm
為什麼離散對數問題很難？
為什麼假設離散對數問題很難？
其他人問了同樣的問題，但答案只解釋了取冪在 $ O(\log(n)) $ 而計算離散對數的已知最快算法是 $ O(n) $ . （我在這裡忽略了諸如索引演算的執行時間之類的細節。）
我在其他地方讀到：“我們假設離散對數很難，因為 40 多年來，非常聰明的人未能找到快速算法。”
現在，我想知道是否有更好的論據。你能真正解釋為什麼離散對數很難嗎？
現在，我想知道是否有更好的論據。
最終，不，不是真的。
我們沒有任何證據表明計算離散日誌很困難。就此而言，我們沒有任何證據表明內部存在任何問題 $ NP $ （也就是說，任何問題，如果答案是“是”，則有一個快速可檢查的證明）是困難的。
我們確實有一些部分證明，例如，在“黑盒”模型中，質數階群上的離散對數是困難的。另一方面，已知的假設對於有限域是錯誤的，因此它沒有人們希望的那麼有用。