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

FIGURE 13.1

Exhaustive Search for Discrete Logs The most obvious solution to finding a dis-
crete logarithm (and by far the slowest) is to search by taking successive powers. For exam-
ple, to solve

b x z (mod n ) 0 < z < n

for x , we simply calculate the lnr's of the sequence

2 , 3 , . . .

b , b b

until we derive z .

E XAMPLE .

Suppose we wish to solve the congruence

257 x 369 (mod 1009)

for . We calculate the successive powers until we obtain a least nonnegative residue of 369

modulo 1009. (See Table 13.2.)
(The successive powers of 257 x go across from left to right.) There are 10 columns in the
table; the last entry (369) is the 104 th entry, so

x

257 104

369 (mod 1009).