Pohlig-Helman Discret Log Algorithm

Given a field GF(q), and a generator g of the field, the logarithm of any non-zero element x of GF(q) to the base g is the integer i such that:

      x = g^i  in GF(q)

For a given x, finding i is the Discret Log Problem.

The Pohlig-Helman algorithm uses the Little Fermat theorem to extract digit by digit the base p representation of i, for any prime p dividing (q-1). All the digits might not be extracted for a single prime. If p^k is the largest power of p dividing (q-1), and the representation of i is:

    i = a_0 + a_1 p + a_2 p^2 + ... + a_l p^l

where each a_j is in 0, ... , p-1, we shall be able to extract digits a_0 up to a_(k-1). That is, we shall have i mod p^k. Doing this for all primes dividing (q-1), the chinese remember theorem will give us i modulo (q-1). Remember that the discret log is unique only up to modulo (q-1), so we will be done.

Little Fermat states that for all invertible x in GF(q), x^(q-1)=1 in GF(q). Suppose that p divides (q-1), we note that:

     x^((q-1)/p) = g^(i(q-1)/p)
                 = g^( (a_0 + a_1 p + ... + a_l p^l)(q-1)/p )
                 = g^( a_0(q-1)/p) g^( (q-1)(a_1 + ... + a_l p^(l-1)) )
                 = g^( a_0(q-1)/p )

Making a table of g^( j(q-1)/p ) for j=0, 1, ... , p-1, we can read of a_0 from x^((q-1)/p).

Next, we remove the a_0 term and take x to the (q-1)/p^2 power, assuming p^2 divides (q-1):

    x_1 = x g^(-a_0)

    x_1^((q-1)/p^2) = g^( (a_1 p + ... + a_l p^l)(q-1)/p^2 )
                    = g^( a_1(q-1)/p ) g^( (q-1)(a_2 + ... + a_l p^(l-2)) )
                    = g^( a_1(q-1)/p )

Refering again to the table, a_1 is discovered. We then remove the a_1 term:

    x_2 = x_1 g^(-a_1 p)

and if p^3 divides (q-1), continue.

We can continue until the largest k such that p^k divides (q-1), where we have,

    x_(k-1) = x^( a_(k-1) p^(k-1) + ... + a)l p^l )

    x_(k-1)^((q-1)/p^k) 
             = g^( (a_(k-1) p^(k-1) + ... + a_l p^l)(q-1)/p^k )
             = g^( a_(k-1)(q-1)/p ) g^( (q-1)(a_k + ... + a_l p^(l-k))
             = g^( a_(k-1)(q-1)/p )

With these numbers, we have:

      i' = a_0 + a_1 p + ... + a_(k-1) p^(k-1)
         = i mod p^k

Having done this for all prime divisors p_1, p_2, ... , p_m of (q-1), we the system of equations:

     i = i_1 mod p_1^(k_1)
     i = i_2 mod p_2^(k_2)
     ...
     i = i_m mod p_m^(k_m)

where

     q-1 = p_1^(k-1) p_2^(k_2) ... p_m^(k_m)

Which can be solved (the Chinese Remainder Theorem) for a unique i modulo q-1.

Burton Rosenberg
6 Sept 2001