Discrete-Logarithm
是否有一個整數模 p 的乘法組，其中離散對數很容易？
以素數為模的乘法群中計算離散對數的複雜性 $ p $ 假定為次指數時間。複雜度由 $ q $ ，組序的最大因素 $ p-1 $ . 有沒有群 $ \mathbb{Z}_p^* $ 這樣離散對數比次指數更容易 $ q $ ?
據我所知，最近關於導出偽多項式效率的離散對數算法的所有進展都發生在小特徵場的情況下 $ GF(p^n) $ 具有結構化指數 $ n $ . 所以最好的複雜性仍然是指數級的 $ \log N $ 在哪裡 $ N $ 是正在考慮的子組的大小。因此，似乎沒有什麼比通用 DL 複雜性更好的了。
您可能會發現以下內容很有趣。Bernstein 和 Lange 已經展示了在允許預處理的情況下通用離散日誌的進步，例如，對於標準中的曲線。
即使在那裡，線上階段的複雜性似乎也是 $ \geq (\log N)^{1/3}. $ 請參閱本文進行討論。這是一個報價：
然而，在實踐中，攻擊者可能有權訪問該組的描述 $ G $ 早在它必須解決離散對數問題實例之前。特別是，絕大多數現實世界的密碼系統使用少數組之一，例如 NIST P-256、Curve25519 或 DSA 組。