Discrete-Logarithm
在群元素的指數中四捨五入
我一直在努力尋找算法 $ \mathcal{A} $ 在下面的。讓 $ (G,g,q) $ 是組參數， $ p << q $ , $ x\in \mathbb{Z}_q $ ，我們可以建立以下算法：
$$ \mathcal{A}(g,g^x,g^{x^k},p,q) = g^{y^k} \text{ where } y = \bigg \lfloor x \cdot \frac{p}{q}\bigg\rfloor \in \mathbb{Z}_p $$
我們可以建構以下算法：
$$ \mathcal{A}(g,g^x,g^{x^k},p,q) = g^{y^k} \text{ where } y = \bigg \lfloor x \cdot \frac{p}{q}\bigg\rfloor \in \mathbb{Z}_p $$
似乎這種適用於任何輸入的算法將允許我們計算離散對數（因此我們希望答案通常是“否”，但是對於某些輸入可能是可能的（儘管我個人對此表示懷疑）。
一種評估離散對數的方法 $ g^x $ 將從評估開始 $ \mathcal{A}(g, g^x, g^x, 2, q) $ （也就是說，與 $ k=1 $ ); 如果 $ x < q/2 $ , 這計算為 $ g^0 $ ， 如果 $ x \ge q/2 $ , 這計算為 $ g^1 $ ，從而將 where 的範圍減半 $ x $ 可能。
然後，我們將跟進 $ \mathcal{A}(g, g^x, g^x, 4, q) $ ，這將使我們能夠將可能的範圍進一步減半 $ x $ . 我們可以繼續前進，直到我們恢復所有 $ x $ ，從而解決了 DLog 問題。