离散对数

在数论中，离散对数 (Discrete logarithm) 是基于原根的对数运算。

离散对数在一些特殊情况下可以快速计算，然而通常没有非常快速的方法来计算它们。（比如模质数时）

---

定义

设 \(a\) 为模 \(m\) 的原根，若 \(a^k \equiv b\pmod{m}\) ，则 \[ \log_ab\equiv k \pmod{m} \] 定义为以 \(a\) 为底模 \(m\)​​ 时的离散对数值。

解释

为什么只有原根为底才行呢？

因为当 \(a\) 是模 \(m\) 的原根时，\(a^0,a^1\cdots a^{\varphi(m)-1}\) 在模意义 \(m\) 下两两不同

否则如果存在两个相同的，那么离散对数就会出现一对多的情况，所以只能用原根。

---

性质

\[ \log_abc\equiv \log_ab + \log_a c \pmod{\varphi(m)} \\[6pt]\log_ax^b\equiv b\log ax\pmod{\varphi(m)} \]

---

参考文献：

[1] https://zhuanlan.zhihu.com/p/523658036