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

定义

当模 m {\displaystyle m} 有原根时,设 l {\displaystyle l} 为模 m {\displaystyle m} 的一个原根,则当 x l k ( mod m ) {\displaystyle x\equiv l^{k}{\pmod {m}}} 时:

I n d l x k ( mod ϕ ( m ) ) {\displaystyle Ind_{l}x\equiv k{\pmod {\phi (m)}}} ,此处的 I n d l x {\displaystyle Ind_{l}x} x {\displaystyle x} 以整数 l {\displaystyle l} 为底,模 ϕ ( m ) {\displaystyle \phi (m)} 时的离散对数值

性质

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

www.zuoweixin.com
问题反馈联系QQ:暂无联系方式,也可发qq邮箱。