關於離散對數問題
經典的離散對數問題是求 $ x\in\Bbb Z_p $ 這樣我們就知道生成器 $ g $ 的 $ Z_p $ 和 $ p $ 是一個素數 $ \frac{p-1}2 $ 索菲日耳曼素數，我們得到 $ h\in\Bbb Z_p $ 這樣 $ g^x\equiv h\bmod p $ 持有。
假設給定 $ g^x\equiv h\bmod p $ 我們知道如何生成 $ g^{x^{2^i}}\bmod p $ 在每一個 $ i\in\Bbb N $ 在 $ O((\log ip)^c) $ 固定時間 $ c>0 $ 是否有助於解決發現 $ x\in\Bbb Z_p $ ?
也知道如何生成 $ g^{x^{2^i}}\bmod p $ 在每一個 $ i\in\Bbb N $ 在 $ O((\log ip)^c) $ 固定時間 $ c>0 $ ?
也知道如何生成 $ g^{x^{2^i}} \bmod p $ 在每一個 $ i \in \mathbb{N} $ 在 $ O((\log ip)^c) $ 固定時間 $ c>0 $ ?
不，不知道；這將立即暗示解決計算 Diffie-Hellman 問題的多項式時間方法，這比目前已知的要好。
這個問題是：給定 $ p, g, g^x \bmod p, g^y \bmod p $ , 計算 $ g^{xy} \bmod p $ .
給定這樣一個 Oracle，我們將如何解決它（從這裡開始，一切都已完成 $ \bmod p $ )：首先，我們可以計算 $ g^x \cdot g^y = g^{x + y} $
然後，我們要求我們的 Oracle 計算 $ g^{x^2} $ , $ g^{y^2} $ , $ g^{(x+y)^2} $ 在 $ O((\log p)^c) $ 時間。
然後我們計算 $ g^{(x+y)^2} \cdot ( g^{x^2} \cdot g^{y^2} )^{-1} = g^{2xy} $
然後，我們取模平方根 $ g^{2xy} $ ，這給了我們 $ g^{xy} $
上述每一步都需要多項式時間。