是在整数中，一种基于同余段见鲁江挥留运算和原根的一种对来自数运算:当模m有原根时，设L为模m的一个原根，则当?x≡L^k(360百科mod m)时: IndLx≡?k (mod Φ(m))，此处的IndLx为 x以整数L为底，模Φ轮移究(m)时的离散对数值。或者简单描述离散对数问题为:给定一个质数p，和有限域Zp上的一条赵配现烈个本原元a，对Zp衡上整数b，寻找唯一的整数c，使得a^c≡b(mod p)。穿木督露例笑马非车一般的，如果仔细选择p，则认为该问题是难解的，且目前还没有找到计算离散对数问题的多项式时间算法。为了抵抗已知的攻击，p至少应该是150位的十进制整数，且p-1至少有一个大的素数因子。

• 中文名称 离散对数
• 提出者 迪菲(W.Diffie)和赫尔曼(E.Hellman)默克勒(R.C.Merkle)
• 应用学科 数学
• 适用领域范围 密码学,计算机技术

离散对数概述

　　是在整数中，一种基于同余运算和原根的一种对脚数运算:当模m有布剂连煤内置跳孙洲原根时，设L为模m的一个原根，则当?x≡L^k(mod m)时: 致路低有月广茶冲识百IndLx≡?k (mod Φ(m))，此处的IndLx为 x以整数L为底，模Φ(m)时的离散对数值。

　　或者简单描来自述离散对数问题为:给定一个质数p，和有限域Zp上的一个本原元a，对Zp上整数b，寻找唯一的整数c，使得a^c≡b(mod p)。一般的，如果仔细选择p，则认为该问题是难解的，且目前还没有找到计算离360百科散对数问题的多项式时间算法。为了抵抗已知的攻击，p至少应该是150位的十进制整数，且p-1至少有绍早一个大的素数因子析密选古审扬。

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

离散对数的由来及发展

　　在一般参考文献中，都认为公钥密码体制是迪菲(W.Diffie)和赫尔曼(E.Hellman)发明的 ，可鲜为人知的是，默克勒(R.C.Merkle)甚至在刻他俩之前的1975年就提出了类似的思想，尽管其文章是于1978年发表的，但投稿比较早。因此，公钥密码体制的创始人应该是他们三人。 当然，他们三热果免人只是提出了一种关于公钥密码体制与数字签名的思想，而没有真正实现妒气鱼判零合道。不过，他们确实是实现了一种体现公钥密码体制思想处留太其查鱼盾苗香、基于离散对数问题的、在不安全的通道上进行密钥形成与交换的新技术。

　　级烟所谓离散对数，就是给定正整数花走呀杀载来x，y，n，求出正整数k(如果存在的话)，使y≡xk(mod n)。就目前而言，人们还没有找到计算离散对数的快速算法(所谓快速算法，是指其计算复杂性在多项式范围内的算法，即O亮映义雨然降游随(logn)k，其中k为常数)。虽然有快速计算离散对数的量子算法，其计算复杂性为O(logn)2+?着，但现在并没有量子计算机(实用的量子计算机也许根本就建造不出来)。

离散对数的应用

　　离散对数公钥加密算法是目前最为热门的公钥加密算法 ，其安全性要远远高于基于大数分解的RSA算法。

　　首先说明一下上述三位科学家公钥密码体制的运作过程(假定A和B两个人要在一个不安全通道如因特网上形成密钥以备日后加密解密所用)。

　　首先，A、B两来自人要共同公开约定一个素数q和有限域Fq中的一个生成元g;

　　A选定一个随机数a∈{1，2，…，q-1}(a可以认为是A之私钥)，并将g a(modq)传送给B;

　　B选定一个随机数b∈{1，2，…，q-1}(b可以认为是B之私钥)，并将gb(modq)传送给A;

　　此时A可以算出(g b)a(modq)，B也可以算出(g a)b(modq)，由于(gb)a(modq) = (g a)b(modq) = g ab(modq)，因此，A和B就形成了一个公共的密钥g ab(mo胞总轮苏dq)，日后便可以此钥来进行传统的加密解密计算，从而达到在不安全的通道上进行保密通讯的目的。

　　显然，敌方可以截获到g，q，g a(modq)，g b(modq范)。因此，如果敌方有快速的求解离散对数的算法，就能从已截获的上述信息中迅速求出a或b，从而算出g ab(modq)。遗憾的是，目前世界上血因二期植晶根本就没有快速的求解离散简达即侵川旧信对数的算法，因此当所选的有360百科限域Fq很大时，a或b就很难算出。

　　 椭圆曲线密码算法(ECC)

　被露影句全　椭圆曲线密码系统(ECC)就是根据除以p的余数的模算术运算来描述模p的离散对数问题。这并不是形成离散对数问题基础的唯一深数学结构。1985年，Neil Koblitz和Victor Miller分别独立提出了椭圆曲线密码系统(ECC)，其安全性依靠将离散对数问题应用于椭圆曲线上林区的点，且存在一些有力的且能用于密码系统的独特性质。ECC即可用于数字签名方案，又可用于加密方案。

　　定义模素数p的椭圆曲线是形如y2=x3+ax+b(地帮待食验mod p)的方程的解(x,y)的集合，a与b是两个数。如果(x,y)满足前述方程，那么p=(x,y)就是椭圆曲线上的点。椭圆曲线也能定义在由2m个元素组成的有限域(finite field)上，此种表示可额外提供ECC运算的效率。可以定义椭圆曲线上的两点的"加法",假设P和Q都是曲线上的点，则P+Q总是曲线上的另一点。

　　椭圆曲线离散对数问题可陈述如下:固定素数p域椭圆曲线，xP简速款正普希律表示P点"加"x次。假定Q是P的倍数,使得对x，有:Q=xP ，那么椭圆曲线离散对数问题是给定P和Q求x。

　　ECC的安全性依赖于椭圆曲线离散对数问题的困难性。与整数因子分解问题和模P的离散对数问题一样，目前没有有效算法解椭圆曲线离散对数问题,

　　ECC的优势之一是椭圆曲线连对数问题被认为比整数因子分解问题和模P的离散对数问题都难。这额外的难度意味着ECC是目前已知的最强公钥密粮火异财正对始岁称标具码系统之一。

离散对数的计算实例

　　下面给出两个计算离散对数的实例。

　　【政副随台见集后实例一】

　　Alice和Bob首先商议好p的值，本例假设为p=2579，则本原元为a=线修全打满推具话判2。

　　假设Alice要发送消息x=1299给Bob，则

　　1)Bob选择随机数r=765作为自己的私钥，计算q=2^r mod p=2^765 mod 2579=949，作为公钥给Alice;

　　2)Alice选择随机数k=853，计算y=2^k mod p=2^853 mod 2579=435，作为公钥给Bob;

　　3)Alice计算密文e=黑田岁让球治最x*q^k mod p=1299*949^853 mod 2579=2396，并传递给Bob;

　　4)Bob接收到密文后，计算x=e*(y^r)^(-1) mod p=2396*(435^765)^(-1) mod 2579=1299，从而得到原文。

　　【实例二】

　　A和B先约定公共的q=2739·(7149-1)/6+1和g=7。

　　A选随机数a，并计算血班坐周7a(modq)，且将其送给B(注:a不能向外泄漏);

　　B将收到7a=127402180119脱推算既相973946824269244334322849749382042586931621654557735290322914679095998681860978813046&595166455458144280588076766033781

　　B选随机数b，并计算7b(modq)，且将其送给A(注:b不能向外泄漏);

　　A将收到7b=18评而距初紧第审城0162285287453124447828348367998950159670&46交富烟龙6953466973130251&217340599537720584759581769106253806广前须响温办车信转脚9210165184866236213793&4026803049。

　　此时A和B都能计算出密钥7ab(modq)，但别人不太容易算出，因为别人不知道a和b。有兴趣的读者不妨将此作为一个练习，试着计算出7ab(modq)的值。

　　(数据中的&是因为百度认为数据中存在电话号码，不让发布，观众可以无视之)