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

i 0 1 2 3 4 5 6 7 8 9

19903 i mod p 1 24783 15001 94125 114711 28838 114917 108096 63848 21941

i 10 11 12 13 14 15 16 17 18

19903 i mod p 71926 56972 122440 84521 81773 80931 71711 5969 38500

We sort this table into

(1 11)

(63848 , 8) (71711 , 16) (71926 , 10) (80931 , 15) (81773 , 14) (84521 , 13) (94125 , 3)
(108096 , 7) (114711 , 4) (114917 , 6) (122440 , 12)

, 0) (5969 , 17) (15001 , 2) (21941 , 9) (24783 , 1) (28838 , 5) (38500 , 18) (56972 ,

Next we compute 101887 × 19903 − j mod p until we hit a value in this table. We compute

19903 − 0

101887 × mod p = 101887

19903 − 1 101887 × mod p = 7139

19903 − 2 101887 × mod p = 114597

19903 − 3 101887 × mod p = 28838

which is in the table, corresponding to i = 5 . So we can check that log 19903 mod p
(101887) 98 . = 3 + 5 × 19 =

Therefore we obtain

y p − 1

359

log g p − 1
359

= 98 .

mod p

Finally, we obtain that log g mod p ( y ) is congruent to 1 modulo 2, to 8 modulo 5 2 ,to4
modulo 7, and to 98 modulo 359. We can now apply the Chinese Remainder Theorem.
We let

x = 1 · r 2 + 8 · r 5 2 + 4 · r 7 + 98 · r 359 mod ( p − 1)

where

p

mod q

− 1

p − 1 − 1

r q = ×

q q

and we obtain that log g mod p ( y ) = x = 23433 .