CODEWITHSUNDEEP
pythonalgorithmcryptography
user448810
user448810

Reputation: 17876

Implementing Pollard's Rho Algorithm for Discrete Logarithms

I am trying to implement Pollard's rho algorithm for computing discrete logarithms based on the description in the book Prime Numbers: A Computational Perspective by Richard Crandall and Carl Pomerance, section 5.2.2, page 232. Here is my Python code:

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

The code includes debugging output to show what is happening. You can run the code at http://ideone.com/8lzzOf, where you will also see two test cases. The first test case, which follows the d > 1 path, calculates the correct value. The second test case, which follows the d == 1 path, fails.

Please help me find my error.

Upvotes: 2

Views: 2764

Answers (1)

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

Problem 1

One thing that looks suspicious is this function:

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

This is computing a modular inverse of x modulo p using Euler's theorem. This is fine if p is prime, but otherwise you need to raise x to the power phi(p)-1.

In your case you are calling this function with a modulo of p-1 which is going to be even and therefore give an incorrect inverse.

As phi(p-1) is hard to compute, it may be better to use the extended Euclidean algorithm for computing the inverse instead.

Problem 2

Running your code for the case g=83, t=566, p=997 produces 977, while you were expecting 147.

In fact 977 is indeed a logarithm of 83 as we can see if we compute:

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

but it is not the one you were expecting (147).

This is because the Pollard rho method requires g to be a generator of the group. Unfortunately, 83 is not a generator of the group 1,2,..997 because pow(83,166,997)==1. (In other words, after generating 166 elements of the group you start repeating elements.)

Upvotes: 4

Related Questions