python - 实现 Pollard 的离散对数 Rho 算法

Question

我正在尝试根据书中的描述实现 Pollard 的 rho 算法来计算离散对数 Prime Numbers: A Computational Perspective作者:Richard Crandall 和 Carl Pomerance，第 5.2.2 节，第 232 页。这是我的 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 提高到幂 phi(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 的对数，如果我们计算就可以看到:

>>> pow(83,977,997)
566

但这不是您所期待的 (147)。

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