密码学 | 3.8 有限域Fp中计算离散对数的索引演算方法

  指数演算法（index calculus）用于在有限域   下计算离散对数。该算法使用了光滑数，和我们前面所学的筛法有一定的相似之处。因此我们把这一知识点放在这里讲，而不是我们讨论离散对数的第二章。

  指数演算法的底层思想其实很简单，我们想要解决离散对数问题

  其实素数 ，整数 已知。方便起见，我们设 为模 下的原根，那么它的幂就能够遍历到 下的所有元素。

  不同于直接求解式 3.27，我们选择一个元素 ，解以下同余式

  即我们计算离散对数 ，其中 是小于 的每个素数。然后，我们计算下面的式子

  当我们找到值 满足 是 的，那么对于这个 ，存在一组 满足：

 我们将 表示成对数的形式

  那么剩下来的，对于所有的 ，我们该如果计算 呢？想法很简单，我们随机的选择指数 ，设

  如果 不是 的，不管它。如果 是 的，那么我们就可以对其进行分解，写作：

  再表示成对数的形式，我们有如下关系

  这种解离散对数的方法叫做指数演算法，其中 “index” 是 2.2 一节中我们讨论离散对数时所涉及的概念。指数验算法第一次出现在 Western 和 Miller 1968年发表的《Tables of Indices and Primitive Roots.》中，因此它比公钥密码术的发明还早了几年。不过在1970s，Diffie-Hellman 的 paper 《New directions in cryptography》发表后，这一方法又被几位密码学家独立的重新发现，

注 3.57 有一个小问题被我们忽略了，就是说式 3.30 实在模 下的同余式组，标准的线性代数方法，比如高斯消元，在模合数的剩余系下可能不会起作用，因为有的元素不存在乘法逆元。但我们可以用中国剩余定理（定理 2.24）来解决这个问题。首先，我们在模 下解同余式组 ，其中 为每一个模 的素数。然后，如果 在 的因子中出现了多次，比如 ,我们就将解从  ”升“ 到 。最终，我们使用中国剩余定理，就将模素数幂下的解组成了模 下的解。因此，在密码应用中，安全起见，我i们应该选择 被大素数整除的数 。否则，我们使用 2.9 一节提到的 Pohlig-Hellman 的算法就能解离散对数了。比如，如果我们选择 ，其中 为素数，那么指数演算法就需要在模 和模 下解式 。

  在指数演算的实际应用中，有许多实现问题和技巧。不过我们在这里不讨论这些问题，只提供一个小的数值例子来说明指数演算是如何工作的

例 3.58 我们有素数 ，然后使用指数演算法求解离散对数问题

  我们注意到 为模 下的原根、我们去 ，那么分解基就是 ，于是我们随机计算 的幂次去找 数。在进行百余次尝试后，我们有

  这些反过来也给出了 在以 为基的离散对数之间的关系，比如通过第一条，我们有

  为了方便表示，我们设

  那么我们有一下线性方程组

  注意到上述线性方程组都是在模 下的。因为上述离散对数是定义在模 下的， 是素数，所以我们需要在模 和模 下对上述方程组进行求解。这里我们使用高斯消元就能很简单的对其进行处理。即通过将一个等式加上另一个等式的倍数来消元。我们可以得到如下解

  在使用中国剩余定理组合一下，我们就有

  可以检查一下

  之后我们随机选择 进行计算，直到 为 数，通过一些尝试，我们得到

  使用上述 的离散对数，我们有

  最后，我们检查一下我们的答案

注 3.59 我们可以大致估算一下指数演算法的时间复杂度。首先，我们要构造一个小于 的素数基，然后需要找到大约 个 的 的数。根据命题 3.48 的建议，我们设 ，然后我们还需要检查大约 个 。此外，还存在检查每个值是否为 的问题，但可以使用筛法来加快该过程约为 的小幂次。在任何情况下，指数演算法都是解决 下离散对数问题的亚指数算法。这与我们将在第 6 章中研究的椭圆曲线群中的离散对数问题形成了鲜明对比。目前，求解椭圆曲线群一般离散对数问题的最著名算法也还是指数级算法。