离散对数Pollard Rho算法的实现

Question

我正在尝试实现Pollard的rho算法来计算离散对数，基于Richard Crandall和Carl Pomerance的书Prime Numbers: A Computational Perspective中的描述，第232页，第5.2.2节。下面是我的Python代码：

def dlog(g,t,p):
    # l such that g**l == t (mod p), with p prime
    # algorithm due to Crandall/Pomerance "Prime Numbers" sec 5.2.2
    from fractions import gcd
    def inverse(x, p): return pow(x, p-2, p)
    def f(xab):
        x, a, b = xab[0], xab[1], xab[2]
        if x < p/3:
            return [(t*x)%p, (a+1)%(p-1), b]
        if 2*p/3 < x:
            return [(g*x)%p, a, (b+1)%(p-1)]
        return [(x*x)%p, (2*a)%(p-1), (2*b)%(p-1)]
    i, j, k = 1, [1,0,0], f([1,0,0])
    while j[0] <> k[0]:
        print i, j, k
        i, j, k = i+1, f(j), f(f(k))
    print i, j, k
    d = gcd(j[1] - k[1], p - 1)
    if d == 1: return ((k[2]-j[2]) * inverse(j[1]-k[1],p-1)) % (p-1)
    m, l = 0, ((k[2]-j[2]) * inverse(j[1]-k[1],(p-1)/d)) % ((p-1)/d)
    while m <= d:
        print m, l
        if pow(g,l,p) == t: return l
        m, l = m+1, (l+((p-1)/d))%(p-1)
    return False

代码包括调试输出，以显示发生了什么。您可以在http://ideone.com/8lzzOf处运行代码，在那里您还将看到两个测试用例。遵循d>；1路径的第一个测试用例计算正确的值。遵循d==1路径的第二个测试用例失败。在

请帮我找出我的错误。在

Answer 1

问题1

有一件事看起来很可疑：

def inverse(x, p): return pow(x, p-2, p)

这是用Euler's theorem计算x模p的模逆。如果p是素数，这是很好的，但否则你需要把x提高到幂φ（p）-1。在

在你的例子中，你用一个p-1的模来调用这个函数，它将是偶数，因此给出了一个不正确的逆。在

由于phi（p-1）很难计算，所以最好使用extended Euclidean algorithm for computing the inverse instead。在

问题2

运行g=83，t=566，p=997的代码生成977，而您预期的结果是147。在

事实上，977确实是83的对数，我们可以看到，如果我们计算：

^{pr2}$

但这不是你所期待的（147）。在

这是因为Pollard rho方法要求g是组的生成器。不幸的是，83不是群1,2，…997的生成器，因为pow（83166997）==1。（换句话说，在生成组的166个元素之后，您开始重复元素。）