Discrete-Logarithm
泛群模型中的離散對數很難 - Shoup 定理
在 Shoups 著名的論文《離散對數和相關問題的下界》中，他證明了離散對數問題在通用群模型中是困難的（如果群運算和逆是唯一可以對群元素執行的計算）。論文中的定理 1 表示一個通用算法的機率 $ A $ 解決這個問題是有界的 $ \mathcal{O}(m^2/p) $ （m 是 oracle 查詢的數量，p 是素數組順序）。我不明白的部分如下：
如果我們堅持 $ A $ 以正常數（例如，1/2）為界的機率成功到以下，該定理轉化為下限 $ \Omega(\sqrt{p}) $ 查詢的組操作數 $ A $ .
有人可以向我解釋這個結論嗎？
讓 $ K $ 是常數（不依賴於 $ p $ ) 使得機率為 $ K\frac{m^2}{p} $ . （一個這樣的 $ K $ 根據定義存在 $ \mathcal{O} $ ).
這意味著如果對手解決離散對數問題的機率大於 $ \frac{1}{2} $ ， 我們獲得。
$$ K\frac{m^2}{p}\geq \frac{1}{2} $$.
這意味著
$$ m\geq \sqrt{\frac{p}{2K}} $$
因此我們推斷 $ m $ - 這實際上是 $ p $ , 下界為 $ K’\sqrt{p} $ ， 和 $ K’:=\sqrt{\frac{1}{2K}} $ 一個不依賴於的常數 $ p $ .
相當於寫 $ m\in \Omega(\sqrt{p}) $ （根據Knuth 表示法）。
現在註意到 $ \sqrt{p} $ 是輸入大小的指數，並且您將推斷任何通用對手對 DLog 無效。