代码之家 › 专栏 › 技术社区 › Robben_Ford_Fan_boy

计算离散对数的PohligHellman算法

discrete-mathematics cryptography math

Robben_Ford_Fan_boy · 技术社区 · 16 年前

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

通过维基百科 algorithm :

我知道第一部分是计算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.

有人能用简单的英语(i)或伪代码来解释这一点吗。显然,我想自己编写解决方案,但除非我理解算法,否则我无法取得任何进展。

注:我已经做了很多搜索这个,我读了S。Pohlig和M。赫尔曼(1978)。”一种计算GF(p)上对数的改进算法及其密码学意义,但对我来说仍然没有意义。

提前谢谢

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

在这个例子中,似乎他正在计算一个新的q time

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

2 回复 | 直到 11 年前

Accipitridae 16 年前

让我们从波利格·赫尔曼背后的主要思想开始。假设我们得到y,g和p,我们想找到x,这样

^十

^K (mod p)是k=p-1。

Pohlig和Hellman提出的是求解这个方程

Y ^N ==(克) ^N ) (国防部p)。

如果我们把对数取为两边的基g,这和

_G (y) ==对数 _G ^N )==新西兰(mod p-1)。

n可以分为

_G

因此x==z(mod r)。

这是一个改进,因为我们只需要搜索范围0。。对于z的解r-1。再次“婴儿步-巨人步”可以用来改进对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 这就意味着我们必须找到这样的z'

^M ==(克) ^M (国防部p)。

因为我们已经知道z'==z(mod q),z'必须在集合{z,z+q,z+2q,…,z+(q-1)q}中。同样,我们可以做一个彻底的搜索z'或改进搜索与“婴儿步巨人步”。对q的每个指数重复这个步骤,这是因为知道x mod q ^我 ^我+1 .

Si. 16 年前

我正在自己编写代码(JAVA)。我用Pollard-Rho求p-1的小素因子,然后用Pohlig-Hellman解DSA私钥。y=g^x。我也有同样的问题。。

更新:“更具体地说,我不明白下面是怎么计算的:现在用7531除以a^c0得到7531(a^2)=6735 mod p。”

如果你找到^c0的倒数,那就有意义了