離散對數問題在二的冪的循環群中很容易
讓 $ G=\langle g\rangle $ 是一個循環的有序群 $ 2^{k} $ 然後讓 $ h\in G $ . 我讀過很容易找到 $ \log _{g} h $ ，但我一直無法弄清楚如何。你知道為什麼這可以在多項式時間內完成嗎？你知道我可以在哪裡找到這本書嗎？
您可能會發現玩一個玩具範例很有用，例如整數模費馬素數，例如 $ p = 257 $ .
自從 $ g $ 是集團的發電機， $ h \equiv g^x $ 對於一些未知的指數 $ x $ . 換句話說， $ \log_gh = x $ , 並且對於順序組 $ 2^k $ ，這個離散對數很容易計算如下：
解釋 $ x $ 作為一個 $ k $ 位數，即 $ x = c_02^0 +c_12^1 + c_22^2 + c_32^3 …+ c_{k}2^{k} $ 其中係數 $ c_0, c_1, c_2…c_k \in {0,1} $ . 你可以找到價值 $ c_0 $ 通過提高 $ g^x $ 對權力 $ 2^{k-1} $ 模組 $ p $ . 如果 $ c_0=0 $ 然後所有其他條款 $ x $ 可被 2 整除，因此 $ x=2y $ ，所以根據歐拉的全定理，
$$ (g^{2y})^{2^{k-1}}\equiv g^{y2^k} \equiv g^0 \equiv 1 \mod p $$ 然而如果 $ c_0 = 1 $ ，然後提高 $ g^x $ 對權力 $ 2^{k-1} $ 反對 $ p $ 將返回結果 $ p-1 $ . 所以通過查看結果，你可以直接看到 $ c_0 $ 是。現在你的價值是 $ c_0 $ , 減去項 $ c_02^0 $ 從 $ x $ （即乘 $ g^x $ 通過模乘逆 $ g^{c_02^0} $ ). 現在你可以找出什麼價值 $ c_1 $ 是，通過使用相同的方法：raise $ g^{x-c_02^0} $ 對權力 $ 2^{k-2} $ . 如果 $ c_1=0 $ ，然後所有剩餘的項 $ x-c_02^0 $ 能被 4 整除，所以 $ x-c_02^0 = 4y $ 和 $ (g^{4y})^{2^{k-2}} \equiv g^{y2^k} \equiv 1 \mod p $ . 另一方面，如果 $ c_1=1 $ 然後結果將是 $ p-1 $ . 減去項 $ c_12^1 $ 從 $ x-c_02^0 $ ，並重複該過程 $ c_2 $ . 繼續直到你發現了所有的係數 $ x $ : 你現在知道什麼了 $ x $ 是。