Appendix D: Technical and Advanced Details - Codes: The Guide to Secrecy from Ancient to Modern Times - page 531

Thus, the base 2 representation of log 2 (19) modulo 4 is

a − 1

b i p i 1 =1 2 0 +1 2 1

· · ≡ 3 (mod 4) . (D.4)

i =0

For p 2 =3 :

k 0 1 2

α ( p − 1) k/p 2 2 12 2 24

1 ≡ 26 ≡ 10

i 0 1

2 − 2

β i 19 19 · ≡ 14

β ( p − 1) /p i [phone] ≡ 10 ≡ 10

2

i

b i 2 2

Thus, the base 3 representation of log 2 (19) modulo 9 is

a 2 − 1

b i p i 2 =2 3 0 +2 3 1 · · ≡ 8 (mod 9) . (D.5)

i =0

Solving (D.4)-(D.5) by the Chinese remainder theorem , we get that

F 37 . e = log 2 (19) = 35 in

1, then given a factorization of n , the running time of the Silver-
Pohlig-Hellman discrete log algorithm is

If n = p −

r

a j ln n + √ p j

O

j =1

group multiplications. This implies that the Pohlig-Hellman algorithm is only
eGcient if the prime divisors of p

1 are small. This is the reason why we talked
about a proper choice of p on page 165 for the intractability of the discrete log
problem.
It should also be noted that the above algorithm makes use of what is known
as the baby-step giant-step algorithm for computing discrete logs due to the
late Dan Shanks, a pioneer in computational number theory. For the sake of
completeness, and because it leads to another important method for computing
discrete logs, we present it here. The following is taken from [170].

−