Let's start with the main idea of Polygus-Hellman. Suppose we are given y, g, and p and that we want to find x such that
y == g x (mod p).
(I use == to indicate an equivalence relation). To simplify things, I also assume that the order of g is p-1, i.e. The smallest positive k with 1 == g k (mod p) is equal to k = p-1.
An inefficient method for finding x is to simply try all the values in the range 1 .. p-1. Somewhat better than the Magic Step method , which requires O (p 0.5 ) arithmetic operations. Both methods are pretty slow for large p. Pohlig-Hellman is a significant improvement when p-1 has many factors. That is, suppose that
p-1 = nr
Then what Pohlig and Hellman suggests is to solve the equation
y n == (g n ) z (mod p).
If we take the logarithms on the basis of g on both sides, then this is the same as
n log g (y) == log g (y n ) == nz (mod p-1).
n can be divided by
log g (y) == z (mod r).
Therefore, x == z (mod r).
This is an improvement since we need to look for the range 0 .. r-1 to solve z. Once again, the “Baby Step” magic step can be used to improve the search for z. Obviously, doing this once is not a complete solution. That is, you need to repeat the above algorithm for each simple factor r p-1, and then use the Chinese theorem on residuals to find x from partial solutions.This works well if p-1 is square.
If p-1 is divided by the main power, then a similar idea can be used. Suppose, for example, that p-1 = mq k . At the first stage, we calculate z so that x == z (mod q), as shown above. Next, we want to extend this to the solution x == z '(mod q 2 ). For instance. if p-1 = mq 2 then this means that we must 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 perform an exhaustive z 'search, or improve the search with the “giant step”. This step is repeated for each exponent q, from knowledge x mod q i iteratively derive x mod q i + 1 .