Double Index Calculus Algorithm: Faster Solving Discrete Logarithm Problem in Finite Prime Field

技术摘要：离散对数问题的双索引演算算法

问题陈述
本文探讨了有限素域中的离散对数问题（DLP），这是一个基础性的计算问题，构成了包括公钥加密和数字签名在内的众多密码体制的安全基石。尽管索引演算算法及其变体（如数域筛法和函数域筛法）代表了在这些域中求解 DLP 的最先进方法，但它们面临特定的局限性。首先，这些算法需要计算因子基（大小为 $k$）中所有素数以及目标整数的离散对数，总计 $k+1$ 个对数，之后才能求解目标。此外，如果 DLP 的底数不是该域的乘法生成元，标准的索引演算算法通常会失效，因为因子基中某些素数的离散对数可能不存在。

方法论：双索引演算算法
作者提出了“双索引演算算法”，该算法通过减少所需的离散对数数量，从根本上改变了求解 DLP 的方法。

1. 双重方程组：算法不再固定单个目标方程，而是构建两个独立的线性方程组：
   • 一个系统计算因子基中素数关于生成元 $g$ 的离散对数（求解 $\log_g p_i$）。
   • 第二个系统计算相同素数关于目标底数 $b$ 的离散对数（求解 $\log_b p_i$）。
2. 交集策略：核心创新在于识别因子基中的一个素数 $p_i$，使得 $\log_g p_i$ 和 $\log_b p_i$ 均已被成功计算。
3. 目标求解：一旦找到这样的素数，算法利用以下关系式求解目标离散对数 $x$（其中 $g^x \equiv b \pmod p$）：
   $$x \equiv \alpha \beta^{-1} \pmod{p-1}$$
   其中 $g^\alpha \equiv p_i \pmod p$ 且 $b^\beta \equiv p_i \pmod p$。
4. 概率效率：该算法依赖于寻找光滑整数的概率特性。虽然标准索引演算算法必须确定性地求解 $k+1$ 个对数，但双索引演算算法只要两组已计算对数的交集非空即可成功。作者认为，“良好情况”（即目标可用少于 $k+1$ 个对数求解的场景）的数量巨大，从而导致高概率的提前终止。
5. 并行化：以 $g$ 为底和以 $b$ 为底的对数计算是独立的过程，允许并行执行，这进一步将总运行时间降低为两个并行过程的最大值，而非它们的总和。

主要贡献

• 理论突破：本文声称在所需离散对数的数量上实现了理论上的减少。传统方法需要 $k+1$ 个对数，而所提出的算法通过利用两组部分对数的交集，可以用少于 $k+1$ 个对数求解该问题。
• 增强的通用性：该算法设计为即使在底数 $g$ 不是域的乘法生成元时也能工作。在这种情况下，如果某些素数的 $\log_g p_i$ 不存在导致标准索引演算可能失效，只要存在至少一个素数使得 $\log_g p_i$ 和 $\log_b p_i$ 同时存在，双索引演算仍可能成功。
• 兼容性：该方法与用于加速寻找光滑整数的现有优化技术（如筛法）兼容。它可以利用这些技巧更快地找到光滑整数，然后应用其自身的逻辑来减少所需光滑整数的数量。

实验结果
作者进行了广泛的实证实验，将其算法与标准索引演算算法及其他经典方法（大步小步法、Rho 算法、Pohlig-Hellman 算法）进行了比较。

• 加速比：对于位长为 70 的有限素域，双索引演算算法相比索引演算算法展示了约 34 倍的加速（2211 秒对比 75426 秒）。
• 可扩展性：随着位长的增加，性能差距扩大。在 50 位时，所提出的算法快了约 10 倍；在 70 位时，快了超过 30 倍。
• 光滑界：实验表明，所提出算法的最佳光滑界与标准索引演算略有不同（通常约为 $0.65B_i$ 对比 $0.5B_i$），但所提出的算法在各种位长（30 至 75 位）下始终保持了更低的平均运行时间。

意义与主张
本文将双索引演算算法定位为求解有限素域中 DLP 的当前最先进方法的重大改进。作者声称，通过减少必须计算的离散对数数量，该算法实现了计算速度的显著提升。他们断言，这种改进不仅仅是现有筛法方法的变体，而是求解过程中的结构性变革。作者建议，这些结果可能会影响研究人员如何为依赖 DLP 困难性的密码体制选择安全参数，因为给定密钥大小的有效安全级别可能低于标准索引演算复杂度模型之前的估计。