Discrete-Logarithm
尋找有多難一世一世i對於序列s一世=Gs我-1反對磷s一世=Gs一世−1反對磷s_{i} = g^{s_{i-1}} mod P和s0=gs0=Gs_0 = g對於給定值v∈[1,P−1]在∈[1,磷−1]vin [1,P-1]
假設我們找到一個常數 $ g $ 和一個素數 $ P $ 它能夠從 $ 1 $ 至 $ P-1 $ 用它的順序 $$ s_{i} = g^{s_{i-1}} \mod P $$ $$ s_0 = g $$
計算需要多少步 $ i $ 對於給定的值 $ v $ ( $ =s_i $ ) 與已知 $ g,P $ ?
能不能比 $ i $ 腳步？
玩具範例：
和 $ P=5, g=3 $ 順序是 $$ \begin{split} &[3, 3^3\equiv 2, 3^{2} \equiv 4, 3^{4} \equiv 1] \mod 5 \ \equiv&[3, 2, 4, 1] \mod 5 \end{split} $$
或為 $ P=23, g=20 $ 值將是： $$ [20,18,2,9,5,10,8,6,16,13,14,4,12,3,19,17,7,21,15,11,22,1] $$ 或者 $ P=59, g=39 $
附帶問題：
- 計算結果需要多少步 $ s_i $ 給定的 $ i,g,P $ ? 比…快 $ O(i) $ ?
- 是否也可以計算 $ s_{i-1} $ 在……之外 $ s_{i} $ ? 還是類似於 DLP？
- 這種序列是否已經有了名字？
這個序列是帶有種子的Blum-Micali 算法的狀態序列 $ g $ .
是否的問題 $ s_i $ 可以在少於 $ i $ steps 是關於生成器是否可以“巨步”的問題。據我所知，我們不知道如何做到這一點。
計算 $ s_{i-1} $ 從 $ s_i $ 正好等價於離散對數問題，用於證明生成器的前向安全性。