跳转到内容

离散对数

维基百科,自由的百科全书

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

定义

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

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

性质

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

参见