离散对数

在数论中，离散对数 (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