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

Question

我正在编写Pohlig-Hellman算法的编码,但是我在根据算法的定义理解算法中的步骤时遇到了问题.

通过算法的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)如何保持不变.

凡在本例中是像他在每次计算新的Q出现时.

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

Answer 1

让我们从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)算术运算的"Baby-step huge-step"方法.对于大p,这两种方法都很慢.当p-1有许多因素时,Pohlig-Hellman是一项重大改进.即假设

p-1 = nr

然后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的解.再次,"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 ²).例如,如果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 ⁱ迭代地导出x mod q ^{i + 1}.