離散日誌問題指數執行時
我試圖了解離散日誌問題的執行時復雜性（在最基本的意義上）。
所以，如果我們有 $ \langle g \rangle = G $ 並試圖找到 $ g^x = a, a \in G, 0 < x < ord(G) $ , 為什麼我們不能只遍歷所有元素 $ G $ 並線上性時間內找到答案？即使我們必須計算 $ g^x $ 通過重複乘法，那不就是二次時間嗎？
那不就是二次時間嗎？
不。
TLDR： 模運算。
您可能會有這樣的印象，即它應該很容易並且只需少量步驟。但是複雜性來自我們使用模組化的事實。例如，在普通算術中，如果 $ a < b $ ， 然後 $ g^a < g^b $ （對於 N）。但是在模運算中沒有這樣的規則。
例子：
讓我們來 $ g = 2099 $ ， 模組 $ M = 2179 $ 並比較 1787、39 和 1279，哪個更大， $ g^{1787} $ , $ g^{39} $ 或者 $ g^{1279} $ ?
$ g^{1787} = 999 $
$ g^{39} = 1000 $
$ g^{1279} = 1001 $
我們看到 $ g^{1787} < g^{39} $ .
對相同數字的其他看法。方程 $ g^x = 1000 $ 有解決方案 $ x = 39 $ . 知道了這一點，我們能猜出方程的解是什麼嗎 $ g^x = 999 $ ? 是否接近 $ 39 $ ? 不，它不接近。的解決方案 $ g^x = 999 $ 是 $ x = 1787 $ . 沒有簡單的相關性。
這就是為什麼在模算術中求解一個方程 $ g^x = 999 $ 我們必須檢查每個數字。如果 $ G = {1, 2, …, 10 000} $ ，我們必須檢查所有這些數字。而如果 $ G = {1, 2, …, 2^{512}} $ ，我們必須檢查所有這些 $ 2^{512} $ 數字。在現實中，一些數學屬性允許我們跳過一些數字組，從而減少所需的計算。儘管如此，即使優化會將其減少到 $ 2^{256} $ ，這仍然是很多工作要做。地球上的全部電腦能力不足以檢查數万億年的所有相關數字。