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

we see that
b x = b q | b | r = ( b

| b | ) qb b r

b r (mod p ).

Now, since b x 1 (mod p ), b r 1 (mod p ) also. But since 0 ≤ r < | b |, we must have r =

0 since | b | is the least positive integer k such that b k 1 (mod p ). Hence, | b | divides x .

b) (Exercise. Hint: use FLT and part (a).)

PROPOSITION 38

Suppose p is prime and b an integer such that p b . Then, if i and
j are nonnegative integers, b i

b j (mod p ) iff i j (mod | b | p ).

Proof.

Suppose i j (mod | b |) and 0 ≤ j ≤ i . Then i = j + k | b | for some positive integer k .

Thus,

b i = b j k | b | = b j ( b

| b | ) k b j (mod p ).

On the other hand, if b i

b j (mod p ), where i ≥ j, we have p b j since p b . Then, note

that since

b i b j b i j b j (mod p )
we can divide this congruence by b j using proposition 21 to obtain

b i j

1 (mod p ).
By proposition 27, we then know that | b | divides i j , or i j (mod | b |).

13.2

GENERATORS

Definition
An integer g such that the prime p does not divide g is called a generator modulo p if
| g | p = p 1.

E XAMPLE .

Note from the previous example that 3 and 5 are generators modulo 7; 1, 2, 4, and

6 are not.

Most cryptosystems that depend on the difficulty of DLP use generators. Thus, we prove
some important facts about generators.

2 , . . .,

PROPOSITION 39 If g is a generator modulo p , then the sequence of integers g , g

g p 1 is a permutation of 1, 2, . . . ., p

1.

Proof. 1 members of the former

sequence are congruent to 0 modulo p , and that none are congruent to each other modulo

To show this, we need only show that none of the p