離散對數：給定 ap，求 x 以 y 為底的離散對數是什麼意思？
我的理解是 $ a^b \bmod p $ 是離散對數問題。鑑於問題的措辭是這樣的，我們是否試圖找到 $ \log_y x \bmod p $ .
例如，如果我們試圖計算以 2 為底的 3 的離散對數 - 假設 $ p=11 $ , 什麼是輸出（或方程）
任意組的離散日誌：離散日誌可以在任意組中定義，有些組可以有一個簡單的解決方案（10 的冪），有些可以有一個困難的解決方案。
讓 $ G $ 是任何組和 $ \odot $ 是團體操作。對於任何 $ k \in \mathbb{Z}_{>0} $ ， 讓 $ b \in G $ 然後我們定義 $ [k]b = \overbrace{b\odot\cdots\odot b}^{{k\hbox{ - }times}} $ . 然後對於給定的 $ a \in G $ 這 $ k $ 滿足 $ [k]b = a $ 稱為離散對數 $ a $ 基地 $ b $ . 它也可以寫成 $ k = \log_b a $
- Additive DLog :的類似定義 $ (\mathbb{Z}_p,+) $ 用給定的定義明確 $ a,b,n $ 尋找 $ x>0 $ 這樣 $ x a \equiv b \bmod n $ . 如果你找到它的倒數，它可以很容易地解決 $ a $ 通過使用Ext-GCD算法。
- 乘法 DLog :，給出了離散對數問題 (DLP) $ a,b,n \in \mathbb{Z}^+ $ 尋找 $ x \in \mathbb{Z}_{>1} $ 這樣 $ a^x \equiv b \bmod n $ , 如果這樣 $ x $ 存在。
對於小模數，我們可以為 DLP 問題建立一個表格，或者您可以在找到您的案例時停止建構表格。
下面是模數為 19 的以 2 為底的 DLog（離散對數）表。
$$ \begin{array}{c|rrrrrrrrrrrrrrrrr} x& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& \color{red}{13}& 14& 15& 16& 17& 18\ \hline 2 ^x \bmod 19& 2& 4& 8& 16& 13& 7& 14& 9& 18& 17& 15& 11& \color{red}{3}& 6& 12& 5& 10& 1 \end{array} $$
例如，給定 3 作為 DLog 以 2 為模 19，我們將在第二行中查找 3 並對應 $ x $ 在 13 的第一行。即 $ 2^{13} \equiv 3 \bmod 19 $
不同的base會產生不同的table；對於基數 5：
$$ \begin{array}{c|rrrrrrrrrrrrrrrrr} x& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13& 14& 15& 16& 17& 18\ \hline 5 ^x \bmod 19& 5& 6& 11& 17& 9& 7& 16& 4& 1& 5& 6& 11& 17& 9& 7& 16& 4& 1 \end{array} $$如果您知道與兩個鹼基的關係，那麼您不需要計算另一個鹼基。
這種方法實際上是蠻力的，並且具有 $ \mathcal{O}(n) $ - 時間複雜度。
暴力破解方法將在以下情況下失敗 $ n \approx 2^{80} $ . DLOG 有更好的搜尋算法，適用於任何組的通用算法；
- Shank 的Baby-Step Giant-Step方法 $ \mathcal{O}(\sqrt{n}\log n) $ -時間和 $ \mathcal{O}(\sqrt{n}) $ -空間。
- 波拉德的 $ \rho $ 方法與 $ \mathcal{O}(\sqrt{n}) $ -time 是 Shank 方法的改進版本。
- 波拉德的 $ \lambda $ 方法（野生和馴服的袋鼠）
- Adleman 指數演算 $ \mathcal{O}(\exp(c \sqrt{\log n \log\log n})) $
- Gordon的NFS 算法 $ \mathcal{O}(\exp(c(\log n)^{1/3}(\log\log(n)^{2/3}) $ -時間
和
- Pohlig–Hellman 算法，適用於組的順序平滑時。它有 $ \mathcal O\left(\sum_i {e_i(\log n+\sqrt {p_i})}\right) $ -時間複雜度 $ \prod_i p_i^{e_i} $ 是群階的素數分解 $ n $ . 為了減輕這種攻擊，這種攻擊必須選擇一個素數順序，它具有相同的最壞情況復雜性 $ \mathcal{O}(\sqrt{n}\log n) $ -時間。
- DLog for Elliptic Curves (Additive)： DLOG 也被定義為 Elliptic Curves，其中給定一個基點 $ G $ 還有一點 $ Q $ 尋找 $ x $ 這樣 $ G = Q $ 在哪裡$$ P = \overbrace{G+\cdots+G}^{{x\hbox{ - }times}} $$
Dlog對於每個 EC 之類的曲線並不難 $ |E(\mathbb{F}_q)|=q $ . 在橢圓曲線密碼學中，我們使用 Dlog 很難的曲線。
上述一些通用算法，Pollard 的 $ \rho $ , 波拉德 $ \lambda $ 也適用於橢圓曲線的 DLog，但基於索引演算的算法和 NFS 除外。EC上找DLog的記錄主要是基於並行Pollard的 $ \rho $ .