离散对数

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

定义

当模 有原根时,设 为模 的一个原根,则当 时:

 ,此处的  以整数 为底,模 时的离散对数值

性质

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

  •  
  •  

参见