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

TABLE 13.3

Inr of
43 j mod 307

j

0 1

1 43

2 7

3 301

4 49

5 265

6 36

7 13

8 252

9 91

10 229

11 23

12 68

13 161

14 169

15 206

16 262

17 214

(We will not sort the table by second component; we will assume that an efficient method
is being used to search the table.) Now, we must compute an inverse of 43 18 modulo 307:
(43 18 ) 299 115 (mod 307).
We now set y = 140, and begin the loop. We show the iterations in the following table.
At each iteration y is set equal to the lnr of its old value times 115 modulo 307. (See Table
13.4.)
We now compute and return the value of x = 4(18) + 15 = 87. You should check that
indeed,

43 87

140 (mod 307).