离散对数

在整数中，离散对数（英语：Discrete logarithm）是一种基于同余运算和原根的一种对数运算。而在实数中对数的定义 log 是指对于给定的 和 ，有一个数 ，使得 = 。相同地在任何群 中可为所有整数 定义一个幂数为 ，而离散对数 log 是指使得 = 的整数 。 离散对数在一些特殊情况下可以快速计算。然而，通常没有具非常效率的方法来计算它们。公钥密码学中几个重要算法的基础，是假设寻找离散对数的问题解，在仔细选择过的群中，并不存在有效率的求解算法。

当模${\displaystyle m}$有原根时，设${\displaystyle l}$为模${\displaystyle m}$的一个原根，则当${\displaystyle x\equiv <!--\; \equiv \; -->l^k(\mathrm{mod}m)}$时：

${\displaystyle In{d}_{l}x\equiv <!--\; \equiv \; -->k(\mathrm{mod}\mathrm{\varphi <!--\; \varphi \; -->}(m))}$，此处的${\displaystyle In{d}_{l}x}$为${\displaystyle x}$以整数${\displaystyle l}$为底，模${\displaystyle \mathrm{\varphi <!--\; \varphi \; -->}(m)}$时的离散对数值

离散对数和一般的对数有着相类似的性质：