离散对数

设 G 为任意的一个组。它的 群体操作 用乘法表示，它的单位元用 1 表示。设 b 是 G 中的任意一个元素。对于任意正整数 k，表达式 b^k 表示 b 自身与其自身 k 倍的乘积:

类似的，令 b^-k 表示 b⁻¹ 与其自身 k 倍的乘积。对于 k = 0 时，则 b 的 k 次幂满足恒等式: b⁰ = 1。

设 a 也是G 的一个元素。方程 b^k = a 的一个整数解：k 被称为 a 的一个以 b 为底的离散对数(在本文中称为对数)。有时写作 k = log_b a 。

2.1 以10为底的幂

用以10为底的幂，构成一个有理数无限子集 G = {…，0.001，0.01，0.1，1，10，100，1000，…}。这个集合 G 是乘法运算下的一个循环群 ，10是一个发生器。对于组中的任何元素 a ，人们都可以计算log₁₀ a。例如，log₁₀ 10000 = 4，和log₁₀ 0.001 = -3。这些是离散对数问题的实例。

实数中的其他以10为底的对数不能作为离散对数问题的实例，因为它们涉及到了非整数指数。例如，等式log₁₀ 53 = 1.724276…意味着10^1.724276… = 53。虽然整数指数可以在任何使用乘积运算和逆运算的组中定义，但是实数中的任意的实数指数需要有比如像 指数函数 这样的其他概念。

2.2 以某固定实数为底的幂

类似的例子也适用于任何非零实数 b。幂构成全为非零实数的乘法子群 G = {…， b⁻³, b⁻², b⁻¹，1， b¹, b², b³，…}。对于 G 中的任何元素 a ，都可以计算log_b a。

2.3 模运算

离散对数最简单的设置之一是组 （Z_p)^×。这是以素数 p 为模的一个乘法组。它的元素是以 p 为模的同余类，并且两个元素的组乘积可以在元素的普通整数乘法运算之后再缩减模 p 得到。

上述组中，一个数的 k 次幂可以通过将其 k 次幂作为整数求出之后，再除以 p 求出余数的方式来计算。当涉及的数字很大时，在计算过程中多次减小模 p 会更加具有效率。不管使用哪种特定算法，都会调用该操作：模幂运算。例如，研究(Z₁₇)^×。为了计算该组中的3⁴ ，计算得到3⁴ = 81，然后用81除以17，得到大小为13的余数。因此在组(Z₁₇)^×中3⁴ = 13。

离散对数就是逆运算。例如，研究关于 k 的方程3^k ≡ 13 (mod 17)。在上面的例子中，一个解是 k = 4，但是这不是唯一的解。由于3¹⁶ ≡1(mod 17)-遵循费马小定理-因此，如果 n 是一个整数，那么就有3⁴⁺¹⁶ⁿ ≡ 3⁴ × (3¹⁶)ⁿ ≡ 13 × 1ⁿ ≡ 13 (mod 17)。因此，这个方程有无穷多个4 + 16n形式的解。此外，因为16是满足3^m ≡ 1 (mod 17)的最小正整数 m ，所以这些是方程仅有的解。等价地，所有可能解的集合可以由一个约束条件来表示，该约束条件为 k ≡ 4 (mod 16)。

2.4 单位元的幂

当在 b 是组 G 的单位元素1的特殊情况下，除1外，a的离散对数log_b a 不存在定义，每个整数 k 都是 a = 1的离散对数。

幂遵从常规的代数恒等式 b^{k + l} = b^k b^l。换句话说，f(k) = b^k 定义的函数

是一个由整数加法群 Z 映射到 b 生成的 G 的子群 H 的群同态。对于 H 中的所有a，log_b a 都存在。相反，对于不在 H 中的 a ，log_b a 不存在 。

如果 H 是无穷大的，那么log_b a 也是唯一的，并且其离散对数相当于一个群同构

另一方面，如果 H 的大小为 n，然后log_b a 仅在模n同余的情况下是唯一的，其离散对数相当于群同构

其中 Z_n 表示以n为模的整数的加法组。

对于普通对数，我们的常见基本变化公式仍然有效:如果 c 是 H 的另一个生成器，那么

离散对数问题被认为是计算上的难题。也就是说，通常没有有效的经典算法用于计算离散对数。

在有限群 G 中，计算log_b a 的一种通用算法是将 b 的幂 k 变得越来越大，直到找到我们所需的 a 。这种算法有时被称为试乘法。这种算法需要执行时间与群 G 的规模呈线性关系，因此执行时间会在组大小值上呈指数增长。因此，它是一个指数时间算法，仅适用于小群体 G 。

有一些比试乘法更加复杂的算法，它们通常是受整数因式分解算法的启发。这些算法比初始算法运行得更快，其中一些算法运行时间与组大小的平方根呈线性关系，因此其运行时间与组大小值的一半呈指数关系。然而，它们都不在多项式时间内运行(以组大小值为标准)。

• 小步大步算法
• 功能场筛算法
• 指数演算算法
• 数字场筛算法
• Pohlig–Hellman算法
• 对数的Pollard's rho算法
• Pollard's kangaroo算法 (又名Pollard's lambda算法)

多亏了Peter Shor，现在我们有了一个高效的量子算法。^[1]

在某些特殊情况下，也存在高效的经典算法。例如，在模 p 的整数加法群中，幂数 b^k 变成一个 bk 的乘积，此等式意味着整数当中的模 p 同余。扩展的欧几里德算法能够更加快速地找到 k 。

虽然离散对数的计算和因式分解整数的计算是不同的问题，但它们具有一些共同的性质:

• 两者都是有限阿贝尔群的隐藏子群问题，
• 这两个问题似乎都很困难(对于非量子计算机，目前还没有有效的算法)，
• 对于这两个问题，量子计算机上的高效算法是已知的，
• 来自一个问题的算法通常适用于另一个问题，并且
• 这两个问题的难度已经被利用来构造各种密码系统。

对于某些组，计算离散对数显然是困难的。在某些情况下(例如，群组(Z_p)^×的大素数阶子群)，不仅没有已知的最坏情况下的有效算法，而且使用随机自归约性可以证明平均情况的复杂度几乎和最坏的情况一样困难。

同时，离散指数运算的逆向问题并不困难(例如，利用平方求幂可以有效地计算出逆问题)。这种不对称性类似于整数因子分解和整数乘法之间的不对称性。这两种不对称性(以及其他可能的单向函数)已被用于构建密码系统。

在离散对数密码系统(DLC)中， G 组的常用选择是循环群(Z_p)^× (例如 ElGamal加密，Diffie-Hellman密钥交换，以及数字签名算法)和有限域上椭圆曲线的循环子群(参见椭圆曲线密码学)。

虽然一般来说没有已知的算法来解决离散对数问题，但是数字场筛算法的前三个步骤只依赖于组 G，而不取决于需要有限对数的 G 中的特殊元素 。经过对于预计算特定组的这三个步骤，只需要执行最后一个步骤就可以获得该组中的特定对数，这比前三个步骤的计算成本低得多。^[2]

事实证明，许多互联网流量会使用级数1024位或级数更低的少数组当中的一个，例如RFC 2409中指定的Oakley素数的循环组。Logjam攻击程序利用此漏洞危害各种互联网服务，这些服务允许使用级数为512位素数的组，即所谓的出口级。^[2]

Logjam攻击程序的作者估计，解决1024位素数的离散对数问题所需的难度更高的预计算，将会被划入美国国家安全局(NSA)等大型国家情报机构的预算之内。 比如。Logjam作者推测，对广泛重用的1024DH素数的预计算，是泄露的美国国安局文件中声称能够破解当前的大部分密码的背后原因。^[2]