2模冪的離散對數算法
對於那些不知道的人，模組化/離散對數問題：
計算 b 給定其他： $ a^b≡c $ 國防部
我知道離散對數沒有通用算法，因此難以處理。( $ O(n^2) $ 更糟糕的是 n 位數通常被認為是棘手的，儘管指數是肯定的）
儘管它不是標準的，但為簡單起見，我將在這裡用第一個字母標記時間複雜性：
- $ M(n) $ 乘法
- $ D(n) $ 用於除法
- $ E(n) $ 求冪
我有兩個條件可以工作：
- d 是 2 的冪，所以 $ d=2^n $ 對於一些已知的 n（這很方便，因為取模，即 $ D(n) $ , 可以用按位 AND 代替，即 $ O(n) $ )
- a 和 c 是奇數，如果不是素數，它們可能會是（這可以推斷，因為 a 必須是奇數才能生成所有其他奇數，其中 c 是一個）
天真的蠻力搜尋將是 $ O(2^nE(n)) $ . 最好的任何算法（我聽說過）都是次指數的 - 仍然不是多項式，這是我的目標。
我有其他一些（非平凡的）算法，即：
（模組化）部門
- $ D(n)=O(n^2) $ 或者
- 用 65536 位數字測試（Python，花了幾秒鐘）
（模組化）求冪
- $ E(n)=O(M(n)n) $ ，就我而言， $ M(n)=O(n^2) $ 所以 $ E(n)=O(n^3) $
- 用 16384 位數字測試（Python，花了幾秒鐘）
離散對數讓我難住了。由於 2 的模數冪允許使用通常不會起作用的各種位旋轉技巧和其他快捷方式，我認為在這種情況下可以在多項式時間內完成。不知道如何。
假設兩個相乘 $ n $ -位整數可以在 $ \mathrm M(n) $ 操作。
這是一個 $ \mathcal O(n^2\cdot\mathrm M(n)) $ 離散對數模算法 $ 2^n $ ，這基本上是適應這個特定問題的Pohlig-Hellman 算法。（使用天真的乘法，因此執行時在 $ \mathcal O(n^4) $ .)
首先，觀察組的順序 $ (\mathbb Z/2^n)^\ast $ 是 $ 2^{n-1} $ : 一個整數 $ {0,\dots,2^n-1} $ 是可逆的模 $ 2^n $ 當且僅當它是奇數時。但是，該組不是循環的；事實上，它的指數是 $ 2^{n-2} $ . 所以，設置 $ k:=n-2 $ 並假設 $ a $ 有訂單 $ 2^k $ 模組 $ 2^n $ . 這是可以達到模數的最大階數 $ 2^n $ ; 特別是，沒有“原始根”模 $ 2^n $ 為了 $ n\geq3 $ . 這也意味著 $ b $ 只能模數唯一確定 $ 2^k $ .
該算法本質上是通過反复“移出”指數中的較高值位直到只剩下一個未知位，然後暴力破解該位來工作的。“移出”位可以通過提高來完成 $ c $ 2的冪：假設二進制展開 $ b $ 是 $ b=\sum_{i=0}^{k-1}2^ib_i $ . 那麼，由於 $ a^{2^l}\equiv0\pmod{2^n} $ 對所有人 $ l\geq k $ ,
$$ c^{2^i} = (a^b)^{2^i} = a^{2^ib} = a^{\sum_{j=0}^{k-1}2^{i+j}b_j} \equiv a^{\sum_{j=0}^{k-1-i}2^{i+j}b_j} \pmod{2^n} \text, $$ 這僅取決於較低的 $ k-i $ 位 $ b $ . 特別是，我們可以從 $ i=k-1 $ ，這將給出
$$ c^{2^{k-1}} \equiv a^{2^{k-1}b_0}\pmod{2^n}\text, $$ 我們可以很容易地確定 $ b_0 $ 通過嘗試這兩個值 $ 0 $ 和 $ 1 $ 並檢查哪一個滿足一致性。（既然我們知道它必須是它們中的任何一個，只插入 $ 0 $ 或者 $ 1 $ 看看它是否匹配也足夠了。） 隨後使用 $ i=k-2 $ 產量
$$ c^{2^{k-2}} \equiv a^{2^{k-2}b_0+2^{k-1}b_1}\pmod{2^n}\text, $$ 既然我們已經知道 $ b_0 $ ，我們可以計算 $ b_1 $ 通過嘗試兩個（或僅其中一個）可能的值。 重複此過程將獲得所有位 $ b $ .
至於執行時：要確定單個位，我們需要計算 $ c^{2^i}\bmod2^n $ 和 $ a^{\sum_{j=0}^{k-1-i}2^{i+j}b_j}\bmod2^n $ . 使用快速取冪，冪模 $ 2^n $ 可以計算在 $ \mathcal O(n\cdot\mathrm M(n)) $ 操作，因此我們需要弄清楚 $ k\in\mathcal O(n) $ 位，總執行時間在 $ \mathcal O(n^2\cdot\mathrm M(n)) $ .
在實踐中，可以通過計算所有值來節省一些操作 $ c^{2^i}\bmod n $ 和 $ a^{2^i}\bmod n $ 提前使用重複平方。然而，這並沒有提高漸近複雜度，因為仍然需要 $ \mathcal O(n) $ 每位乘法 $ b $ 組合記憶體的值 $ a^{2^i}\bmod n $ 根據具體的已知位 $ b $ .