4

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

通过算法的维基：

我知道第一部分 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) 如何保持不变。

在这个例子中，他每次都在计算一个新的q。

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

4

2 回答 2

7

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

y == g x (mod p)。

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

找到 x 的一种低效方法是简单地尝试 1 .. p-1 范围内的所有值。稍微好一点的是需要 O(p 0.5 ) 算术运算的“小步巨步”方法。对于大 p，这两种方法都非常慢。当 p-1 有许多因素时，Pohlig-Hellman 是一个显着的改进。即假设

p-1 = nr

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

y n == (g n ) z (mod p)。

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

n log g (y) == log g (y n ) == nz (mod p-1)。

n 可以被划分出来，给出

log g (y) == z (mod r)。

因此 x == z (mod r)。

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

如果 p-1 可以被一个素数整除，那么可以使用类似的想法。例如，假设 p-1 = mq k。在第一步中，我们计算 z 使得 x == z (mod q) 如上所示。接下来我们要将其扩展到解决方案 x == z' (mod q 2 )。例如，如果 p-1 = mq 2那么这意味着我们必须找到 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 q i我们迭代推导出 x mod q i+1。

于 2010-04-04T20:05:10.427 回答
1

I'm coding it up myself right now (JAVA). I'm using Pollard-Rho to find the small prime factors of p-1. Then using Pohlig-Hellman to solve a DSA private key. y = g^x. I am having the same problem..

UPDATE: "To be more specific I don't understand how the following is computed: Now divide 7531 by a^c0 to get 7531(a^-2) = 6735 mod p."

if you find the modInverse of a^c0 it will make sense

Regards

于 2010-04-03T19:48:49.037 回答