Algorithmic Number Theory - A Classical Introduction to Cryptography: Applications for Communications Security - page 205

21153 3 mod p = 52301

21153 4 mod p = 91649

Therefore

y p − 7

log g p − 1
7

= 4 .

mod p

y

5 2 .Wehave

p − 1

Let us now compute log g p − 1

5 2

mod p

p − 1 p − 1

6 5026 123 5026

g mod p = mod p = 45194 , y mod p = mod p = 34726 .

5 2 5 2

We know that this logarithm is in a group of order 5 2 . We can have a first approximation
(compute the modulo 5 part) by computing log 45194 5 mod p (34726 5 ) .Wehave 45194 5

mod

55981 , so we need to compute log 10770 mod p (55981) in a
group of order 5. Since 5 is quite small, we make a logarithm table.

10770 and 34726 5 p = mod p =

10770 1 mod p = 10770

10770 2 mod p = 17027

10770 3 mod p = 55981

10770 4 mod p = 41872

10770 5 mod p = 1 .

Thus log 10770 mod p (55981) = 3 . Therefore log 45194 mod p (34726) mod 5 = 3 . owe

can take 10770 , and we notice that its logarithm in 34726 / 45194 3 mod p =

base 10770 is 1. So we can check that 8 .

log 45194 mod p (34726) = 3 + 1 × 5 =

Therefore

y

5 2

p − 1

log g p − 1 = 8 .

5 2

mod p

y p − 1

359 .Wehave

Let us finally compute log g p − 1
359

mod p

g p − 1 y p − 1 6 350 123 350

359 mod p

= mod p = 19903 ,

359 mod p

= mod p = 101887 .

We need to compute log 19903 mo d p (1 01887) in a group of order 359. For this we need the

Shanks algorithm. Let = √ 359 = 19 be the “giant step.” We compute the table of
powers of 19903 mod p for powers up to 18: