离散对数

未解决的计算机科学问题：是否存在离散对数问题的多项式时间经典算法？

在整数中，离散对数（英语：Discrete logarithm）是一种基于同余运算和原根的一种对数运算。而在实数中对数的定义 $\log _{b}a$ 是指对于给定的 $a$ 和 $b$ ，有一个数 $x$ ，使得 $b^{x}=a$ 。相同地在任何群 G中可为所有整数 $k$ 定义一个幂数为 $b^{k}$ ，而离散对数 $\log _{b}a$ 是指使得 $b^{x}=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 yInd_{l}x{\pmod {\phi (m)}}$

参见

原根
对数