math - 用于计算离散对数的 Pohlig-Hellman 算法

Question

我正在编写 Pohlig-Hellman 算法，但我在根据算法定义理解算法中的步骤时遇到问题。

通过 algorithm 的 Wiki :

我知道第一部分 1) 是计算 p-1 的素数 - 这很好。

但是，我不确定在计算系数的步骤 2) 中需要做什么:

Let x2 = c0 + c1(2). 
125(180/2) = 12590 1 mod (181) so c0 = 0.
125(180/4) = 12545 1 mod (181) so c1 = 0.
Thus, x2 = 0 + 0 = 0.

3) 把这些系数放在一起，用中国剩余定理求解。

有人可以帮助用简单的英语 (i) 或伪代码解释这一点。我显然想自己编写解决方案，但除非我了解算法，否则我无法取得更多进展。

注意:我为此做了很多搜索，并阅读了 S. Pohlig 和 M. Hellman (1978)。 “一种用于计算 GF(p) 上的对数及其密码意义的改进算法，但对我来说仍然没有意义。

提前致谢

更新:
为什么 q(125) 在 this example 中保持不变.

在这个例子中，看起来他正在计算一个新的 q time .

更具体地说，我不明白如何计算以下内容:
现在将 7531 除以 a^c0 得到 7531(a^-2) = 6735 mod p .

Answer 1

让我们从 Pohlig-Hellman 背后的主要思想开始。假设我们给定了 y、g 和 p 并且我们想要找到 x，使得

y == g^x (mod p).

(我使用 == 来表示等价关系)。为简化起见，我还假设 g 的阶数为 p-1，即具有 1==gk (mod p) 的最小正 k 为 k=p-1。

查找 x 的一种低效方法是简单地尝试 1 .. p-1 范围内的所有值。
更好的是 "Baby-step giant-step"需要 O(p0.5) 算术运算的方法。对于大 p，这两种方法都很慢。当 p-1 有很多因素时，Pohlig-Hellman 是一个显着的改进。 IE。假使，假设

p-1 = n r

那么 Pohlig 和 Hellman 提出的就是解方程

yⁿ == (gⁿ)^z (mod p).

如果我们对两边的基 g 取对数，这与

n log_g(y) == log_g(yⁿ) == nz (mod p-1).

n 可以被除，给出

log_g(y) == z (mod r).

因此 x == z (mod r)。

这是一个改进，因为我们只需要在 0 .. r-1 范围内搜索 z 的解。再次“婴儿步巨步”可用于改进对 z 的搜索。显然，这样做一次还不是一个完整的解决方案。 IE。必须对 p-1 的每个素因数 r 重复上述算法，然后使用中国剩余定理从部分解中找到 x。如果 p-1 是无平方的，这很有效。

如果 p-1 可以被质数幂整除，那么可以使用类似的想法。例如，让我们假设 p-1 = m qk。
在第一步中，我们计算 z 使得 x == z (mod q) 如上所示。接下来，我们要将其扩展为解决方案 x == z' (mod q2)。例如。如果 p-1 = m q2 那么这意味着我们必须找到 z' 使得

y^m == (g^m)^z' (mod p).

由于我们已经知道 z' == z (mod q)，所以 z' 必须在集合 {z, z+q, z+2q, ..., z+(q-1)q } 中。同样，我们可以对 z' 进行详尽的搜索，也可以使用“baby-step Giant-step”来改进搜索。对 q 的每个指数重复此步骤，这是从知道 x mod qi 我们迭代地推导出 x mod qi+1。