离散对数
离散对数（英语：Discrete logarithm）是一种基于同余运算和原根的对数运算。在数论和密码学领域中被广泛运用，在有限域或循环群中，离散对数问题可以是给定一个生成元和一个元素，找到一个整数作为指数，使得生成元的该指数次幂等于给定的元素。
在一般参考文献中，都认为公钥密码体制是迪菲(W. Dife)和胡安·赫尔曼( E. Hellman)发明的，可鲜为人知的是，默克勒(R. C. Merkle)甚至在他俩之前的1975年就提出了类似的思想，尽管其文章是于1978年发表的，但投稿比较早。
离散对数的通用算法包括量子算法、Pohlig-Hellman方法、小步－大步法和Pollard Rho方法等。
定义
离散对数
离散对数概述，是在整数中，一种基于同余运算和原根的一种对数运算，当模有原根时，设为模的一个原根，则当时，，此处的为x以整数L为底，模时的离散对数值。
离散对数问题
离散对数问题为，给定一个质数和有限域上的一个本原元，对上整数，寻找唯一的整数，使得。一般的，如果仔细选择，则认为该问题是难解的。为了抵抗已知的攻击，至少应该是150位的十进制整数，且至少有一个大的素数因子。
历史
在一般参考文献中，都认为公钥密码体制是迪菲(W. Dife)和胡安·赫尔曼( E. Hellman)发明的，可鲜为人知的是，默克勒(R. C. Merkle)甚至在他俩之前的1975年就提出了类似的思想，尽管其文章是于1978年发表的，但投稿比较早。因此，公钥密码体制的创始人应该是他们三人。他们三人只是提出了一种关于公钥密码体制与数字签名的思想，而没有真正实现。他们确实是实现了一种体现公钥密码体制思想、基于离散对数问题的、在不安全的通道上进行密钥形成与交换的新技术。所谓离散对数，就是给定正整数, ,,求出正整数 (如果存在的话)，使。就目前而言，人们还没有找到计算离散对数的快速算法(所谓快速算法，是指其计算复杂性在多项式范围内的算法，即, 其中为常数)。虽然有快速计算离散对数的量子算法，其计算复杂性为,但现在并没有量子计算机(实用的量子计算机也许根本就建造不出)。
相关概念
在数论中的离散对数指的是：设为奇素数，是的原根，不能整除整数，则存在整数，使得。其中称为对模数的离散对数。
性质
离散对数和一般的对数有着相类似的性质，给定正整数， ， ，求出正整数(如果存在的话)，使。
通用算法
随机自归约和比特困难性
在密码学应用中更多是按照一定的分布随机选择平均情况的实例，平均情形的困难性和最坏情形困难性的关系对于密码应用具有重要意义。离散对数问题通过随机化方法可以建立最坏情况到一般情况的自归约。假定要求的目标元素是，可以选取随机数编辑器，计算平均情形的实例，如果可以求解，就可以对应求解出。一些格上的困难问题也可以建立最坏情况到一般情况的归约，如最小整数解问题（ShortlntegerSolution，SIS）和容错学习问题（LearningWithEr-rors，LEW）。区别是离散对数是同一个群上的归约，而后者是从任意的格归约到给定的平均情形困难问题。考虑一般循环群上的离散对数问题，如果上的离散对数是困难的，Hasta等证明对于随机选取的满足，的二进制表示为比特，那么的到比特以很高的概率是求解困难的。
量子算法
整数分解问题和离散对数问题是公钥密码学应用最广泛的2类困难问题，针对2者的求解算法也有相似之处，包括量子算法和经典算法。Shor设计了量子算法求解整数分解问题和素域上的离散对数问题。2者都可以看作特殊的隐藏子群问题，例如，基于有限循环群上的离散对数计算等价于求解下面映射的核：，其中，。更一般地，求解基于交换群的隐藏子群问题有高效的量子算法。下面讨论经典计算模型（如Turing机）下求解离散对数问题的算法。
Pohlig-Hellman方法
Pohlig等提出了一种约化方法，假设已知群阶的素分解，目标是求解，可以通过如下步骤将问题约化为素数循环群上的离散对数求解。首先，利用孙子定理，可以将求解 转化为求解 ，，从而问题转化为阶为素数幂循环群的离散对数求解。其次，可以将阶为素数幂的离散对数求解转化为阶为素数的离散对数求解。例如，为了求解，不妨假设，其中，。记，，则生成一个阶为的循环子群，。令，，则生成一个阶为的循环子群，可以由穷搜或者结合接下来介绍的通用算法求解。进一步，令，则。其余类似可得。
小步－大步法
Shanks利用时间空间折中的思想设计了求解离散对数的小步－大步法，该方法是确定性求解算法，而且渐进复杂度优于穷搜法。记，利用带余除法，可以将待求的离散对数写成，，，为了求解对应的a,b，注意到有等式（碰撞）。可以通过寻找碰撞的方法求解。首先，计算,并存储在一个排序的列表中（可以存储在二元树、哈希表，或者存储后排序）。然后，计算并判断是否和上一个列表中的元素重复（即发生碰撞）。找到碰撞之后，可以通过对应的恢复离散对数。小步－大步法的时间和空间复杂度为，其中，，为一个常数。一些研究者尝试构造多个形如的列表以提高寻找碰撞的效率。
Pollard Rho方法
针对基本的离散对数问题，Pollard基于生日碰撞的思想设计了Rho方法。假设找到碰撞，从而。如果，那么可以求解。为了能够以较低的空间找到所需的碰撞，Rho方法结合了伪随机游走和Floyd寻找碰撞的技术。Pollard将划分成3个互不相交的集合。选定初始值，定义如下伪随机游走序列，
对应的可以得到的迭代公式。为了找到碰撞，在第步保存信息并判断是否。Rho算法的分析在启发式假设下采用了生日碰撞问题的结论，算法的平均时间复杂度为次群运算，空间复杂度为。研究者后续提出了针对Rho方法的许多改进，包括采用并行计算、群的划分以及使用其他形式的随机游走等。Kuhn等推广了Rho方法求解个目标元素的离散对数，算法复杂度为。
Pollard袋鼠算法与Gaudry-Schost方法
针对小区间离散对数问题，Pol-lard提出了袋鼠科算法，也称Lambda方法。在袋鼠算法中有2类游走，一类是家袋鼠游走，另一类是野袋鼠游走。与Rho方法中的游走类似的是，Lambda方法中袋鼠的游走是由现在的值所对应的分类决定；不同的是，步长集团按照预计算的一些小步决定。Lambda方法的分析不是基于生日碰撞问题，而是基于其他概率分析，其复杂度为。Van Ooschot和Wiener使用了区分点技术来降低存储，将一次大整数乘法分解为多次小整数乘法提高运算效率。针对高维离散对数问题，Gaudry等用伪随机游走结合区分点的算法。区分点是一些预先设定的具有良好的统计性质但又可以高效检验的元素。Gaudry-Schost算法求解高维离散对数的时候，先随机选取一个起始点，然后采用随机游走，到达某一区分点后记录信息，最后重新开始新的随机游走。当2个不同类型的游走（形如和）达到同一区分点时（发生碰撞），即可以计算出所求的离散对数。该算法的复杂度与Lambda方法类似，均为，其中，为搜索空间大小。计算1维区间上离散对数问题的最快方法由Galbraith等提出，他们分别利用4个袋鼠和调节碰撞区间加速了Lambda方法和Gaudry-Schost算法。算法复杂度仍为级别，在前面的系数上有所改进。
特殊算法
给定定义在有限域上的椭圆曲线有理点，椭圆曲线离散对数问题是求解最小整数，使得。实际使用一般是基于一个阶数比较大的循环子群。该问题是椭圆曲线密码学安全性的基石，在双线性对密码学中也是安全性基础之一。根据Hasse定理，定义在上椭圆曲线有理点的个数满足，其中，称为的迹。
参考资料
密码学顶级智力较量:西电胡予濮攻破GGH密码方案.西安电子科技大学综合信息服务网.2024-01-20
密码学和计算数论.外部链接.2024-01-20
什么是离散对数问题？为什么它被认为在计算上难以解决？.欧洲信息技术认证学院-检验您的专业数字技能.2024-01-20
Diffie-Hellman 协议有多少个公共参数？.欧洲信息技术认证学院-检验您的专业数字技能.2024-01-20