离散对数，是数学科学中的词语，离散对数和一般的对数有著相类似的性质。

离散对数

是在整数中，一种基于同余运算和原根的一种对数运算 当模m有原根时，设l为模m的一个原根，则当时： ，此处的Indlx为x以整数l为底，模φ(m)时的离散对数值 性质 离散对数和一般的对数有著相类似的性质： 所谓离散对数,就是给定正整数x,y,n,求出正整数k(如果存在的话),使y≡xk(mod n)。

离散对数解

1976年，美国斯坦福大学教授赫尔曼(E.Hellman)和他的研究助理迪菲(W.Diffie)，

以及博士生默克勒(R.C.Merkle)（简称为DHM）首先创立并发表了所谓的“公钥密码体制”（public key cryptography），即加密、解密用两个不同的钥，加密用公钥（public key），即可以公开，不必保密，任何人都可以用；解密用私钥（private key），此钥必须严加管理，不能泄漏。更为称绝的是，他们还发明了所谓的数字签名（digital signatures）技术，即用私钥签名，再用公钥验证。

在一般参考文献中，都认为公钥密码体制是迪菲和赫尔曼发明的[1]，可鲜为人知的是，默克勒甚至在他俩之前的1975年就提出了类似的思想，尽管其文章是于1978年发表的[2]，但投稿比较早。因此，公钥密码体制的创始人应该是DHM三人，这种观点目前已得到了国际上的认同，尤其得到了赫尔曼教授本人的认定。当然，英国军用情报中心也曾宣称他们早在1970年就发明了公钥密码体制，但经仔细分析其资料并与中心有关人员讨论后发现，他们只是提及了公钥密码体制的某种特殊形式。更为重要的是，DHM的公钥密码体制还包含数字签名，而情报中心的资料则是只字未提。注意，美国国家安全局也有过类似的宣称，不过这都是不可信的（至少不可全信）。如要详细了解公钥密码体制的发展史，读者可参考笔者的一本由赫尔曼教授作序的英文专著[3]。

当然，DHM只是提出了一种关于公钥密码体制与数字签名的思想，而没有真正实现。不过，他们确实是实现了一种体现公钥密码体制思想、基于离散对数问题的、在不安全的通道上进行密钥形成与交换的新技术。这里必须先介绍一下什么叫离散对数。

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

现在，说明一下DHM的运作过程（假定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(modq)，日后便可以此钥来进行传统的加密解密计算，从而达到在不安全的通道上进行保密通讯的目的。

显然，敌方可以截获到g，q，g a(modq)，g b(modq)。因此，如果敌方有快速的求解离散对数的算法，就能从已截获的上述信息中迅速求出a或b，从而算出g ab(modq)。遗憾的是，目前世界上根本就没有快速的求解离散对数的算法，因此当所选的有限域Fq很大时，a或b就很难算出。值得注意的是，DHM密钥交换体制实际上是一座沟通密钥密码体制与公钥密码体制的桥梁，即用公钥密码体制的思想形成密钥（虽然公钥密码体制计算速度慢，但密钥的长度一般都很短，所以没有关系），再用密钥进行传统的密钥密码体制的加密与解密运算（密钥密码体制的运算速度一般都很快，所以适合于对容量大的信息进行加密解密计算）。在这里，这两种密码体制交叉使用，扬长避短，充分发挥了各自的优越性。

下面给出一个关于具体计算离散对数的实例。

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

A选随机数a，并计算7a(modq)，且将其送给B（注：a不能向外泄漏）；