离散对数

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

定义

当模$m$有原根时，设$l$为模$m$的一个原根，则当$x \equiv l^k \pmod{m}$时：

$Ind_{l} x \equiv k \pmod{m}$，此处的$Ind_{l} x$为$x$以整数$l$为底，模$m$时的离散对数值

性质

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

• $Ind_{l} xy \equiv Ind_{l} x + Ind_{l} y \pmod{\phi (m)}$
• $Ind_{l} x^y \equiv y Ind_{l} x \pmod{\phi (m)}$

参见

• 原根
• 对数