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

Let c = 1 and compute b * = (5 ) 40/2 1 1 (mod 41).

Compute d 0 = log 40 1 = 2 (by using, for example, baby-step giant-step).

Now, let c = 1 6 2

36 (mod 41) and compute b * = (5 36 ) 40/4 1 (mod 41).

Compute d 1 = log 40 1 = 2 (by using, for example, baby-step giant-step).

Now, let c = 1 6 1 2

36 (mod 41) and compute b * = (5 36 ) 40/8 1 (mod 41).

Compute d 2 = log 40 1 = 2 (by using, for example, baby-step giant-step).

This yields

x 1 = 2 + 2 2 + 2 2 2 = 14.

Now, to compute x 2 :

g * = 6 40/5

10 (mod 41)

Let c = 1 and compute b * = (5 1 ) 40/5

18 (mod 41).
Compute d 0 = log 10 18 = 2 (by using, for example, baby-step giant-step).

This immediately yields

x 2 = 2.
Thus, we seek a solution to the system of congruences

6 (mod 2 3 )

x 14

x 2 (mod 5).

By using the Chinese Remainder Theorem, we derive the solution

x 22 (mod 40).

Thus, log 6, 41 5 = 22. (Verify!)

Now, to the index-calculus algorithm. But before we describe it, we should cover some
properties which discrete logarithms possess; they are very similar to properties of logarithms
of real numbers.

PROPOSITION 43 Let p be prime, and let g be a generator modulo p . Suppose a and b
are positive integers not divisible by p . Then we have all of the following:

a) log1 0 (mod p 1)
b) log( ab ) log a + log b (mod p 1)
c) log( a k ) k log a (mod p 1)

where all logarithms are to the base g modulo p .