Discrete-Logarithm
是什麼讓離散對數問題變得困難？
我錯過了 DLP 背後的關鍵數學部分，我希望有人能給我一個非常愚蠢的答案。
如果 $ h=g^x \bmod p $ 我們正在小組中工作 $ Z^_p $ , 為什麼我找不到 $ x $ 在給定的線性時間內，我有 $ h, g, p $ ， 和 $ Z^_p $ ? 我最多有 $ \operatorname{ord}(Z^*_p) $ 要執行的迭代？
我看不出我顯然誤解了數學的哪個方面。計算不是線性的嗎 $ g^x \bmod p $ 對於一些 $ x $ ? 這是我唯一的猜測。
確實，在最壞的情況下你有 $ \operatorname{ord}(Z^_p) $ 要測試的值。然而，問題的複雜性實際上是根據問題在電腦表示中的輸入大小來衡量的，它是二進制的。這裡我們問題的輸入是 h 和 p。這兩個都是大小的整數 $ log_2(p) $ 最多以電腦二進製表示。該算法將採取 $ \operatorname{ord}(Z^_p) = p $ 迭代。然而， $ p = 2^{log_2(p)} $ ，所以我們可以清楚地看到，所需的迭代次數實際上是問題輸入大小的指數。這就是離散對數問題很難的原因。
當您通常看到表單的複雜性時 $ O(n) $ 或者 $ O(log(n)) $ ，我們實際上假設我們的問題的大小是 $ n $ 在電腦表示中，沒有明確說明。