Exponential Congruences - Introduction to Cryptography with Java Applets - page 250

One step may require clarification; namely, step 1.(a).III: How do we know that

d k = log g * b *

is indeed the k th digit in the p i -ary representation of x i ? Note first that if q = p i and e = e i
as in the algorithm, we have | g * | = q . During the k th loop of step 1.(a).III, we have

c = g k− 1 k− 1 +···+d 1 q+d 0

and so

b * = ( b / c ) n / qk 1

= ( g x d k 1 qk 1 d 1 q d 0 ) n / qk 1

= ( g n / qk 1 ) x i d k 1 qk 1 d 1 q d 0

(switch order of exponents)

= ( g n / qk 1 ) d e 1 qe 1 ... d k qk

= ( g n / q ) d e 1 qe 1 k ... d k (divide and multiply by q j )

= ( g * ) d k (since | g * | = q )

Thus, we indeed have d k = log g * b * .

Note that in order for us to compute a logarithm with Pohlig-Hellman, we need to know
the prime factorization of p

1, and to compute other logarithms (specifically, step 1.(c).III.).
We must use another algorithm to compute these logs; for example, baby-step giant-step.
If one of the factors of p 1 is large, then computing this “sublogarithm” is also an

intractable problem.
Admittedly, the notation in this algorithm looks virtually labyrinthine; however (as usual),
an example will show how straightforward it really is. We will use small parameters.

E XAMPLE . Let the prime p = 41. We can easily obtain the prime power factorization of

p 1:

p 1 = 40 = 2 3 5

We want to find log 6,41 5; that is, the solution to 6 x

5 (mod 41).
To do this, we must compute each of the following:

1. x 1 x (mod 2 3 )

→ x 1 = d 0 + d 1 2 + d 2 2 2

2. x 2 x (mod 5)

→ x 2 = d 0

We begin with x 1 :

g * = 6 40/2

40 (mod 41).