Pohlig–Hellman algorithm for computing discrete logarithms

Question

Hi Folks, I'm working on coding the Pohlig-Hellman Algorithm but I am having problem understand the steps in the algorithm based on the definition of the algorithm.

Going by the Wiki of the algorithm: http://en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm

I know the first part 1) is to calculate the prime factor of p-1 - which is fine.

However, I am not sure what I need to do in steps 2) where you calculate the co-efficents:

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.

and 3) put the coefficents together and solve in the chinese remainder theorem.

Can someone help with explaining this in plain english (i) - or pseudocode. I want to code the solution myself obviously but I cannot make any more progress unless i understand the algorithm.

Note: I have done a lot of searching for this and I read S. Pohlig and M. Hellman (1978). "An Improved Algorithm for Computing Logarithms over GF(p) and its Cryptographic Significance but its still not really making sense to me.

Thanks in advance

Update: how come q(125) stays constant in this example: http://www-math.cudenver.edu/~wcherowi/courses/m5410/mid02.html#ans3

Where as in this example is appears like he is calculating a new q each time:L http://www-math.cudenver.edu/~wcherowi/courses/m5410/phexam.html

To be more specific I don't understand how the following is computed: Now divide 7531 by a^c0 to get 7531(a^-2) = 6735 mod p.

Answer 1

Hi,

I'm coding it up myself right now (JAVA). I'm using Pollard-Rho to find the small prime factors of p-1. Then using Pohlig-Hellman to solve a DSA private key. y = g^x. I am having the same problem..

UPDATE: "To be more specific I don't understand how the following is computed: Now divide 7531 by a^c0 to get 7531(a^-2) = 6735 mod p."

if you find the modInverse of a^c0 it will make sense

Regards

Answer 2

Let's start with the main idea behind Pohlig-Hellman. Assume that we are given y, g and p and that we want to find x, such that

y == g^x (mod p).

(I'm using == to denote an equivalence relation). To simplify things, I'm also assuming that the order of g is p-1, i.e. the smallest positive k with 1==g^k (mod p) is k=p-1.

An inefficient method to find x, would be to simply try all values in the range 1 .. p-1. Somewhat better is the "Baby-step giant-step" method that requires O(p^0.5) arithmetic operations. Both methods are quite slow for large p. Pohlig-Hellman is a significant improvement when p-1 has many factors. I.e. assume that

p-1 = n r

Then what Pohlig and Hellman propose is to solve the equation

yⁿ == (gⁿ)^z (mod p).

If we take logarithms to the basis g on both sides, this is the same as

n log_g(y) == log_g(yⁿ) == nz (mod p-1).

n can be divided out, giving

log_g(y) == z (mod r).

Hence x == z (mod r).

This is an improvement, since we only have to search a range 0 .. r-1 for a solution of z. And again "Baby-step giant-step" can be used to improve the search for z. Obviously, doing this once is not a complete solution yet. I.e. one has to repeat the algorithm above for every prime factor r of p-1 and then to use the Chinese remainder theorem to find x from the partial solutions. This works nicely if p-1 is square free.

If p-1 is divisible by a prime power then a similiar idea can be used. For example let's assume that p-1 = m q^k. In the first step, we compute z such that x == z (mod q) as shown above. Next we want to extend this to a solution x == z' (mod q²). E.g. if p-1 = m q² then this means that we have to find z' such that

y^m == (g^m)^z' (mod p).

Since we already know that z' == z (mod q), z' must be in the set {z, z+q, z+2q, ..., z+(q-1)q }. Again we could either do an exhaustive search for z' or improve the search with "baby-step giant-step". This step is repeated for every exponent of q, this is from knowing x mod qⁱ we iteratively derive x mod qⁱ⁺¹.