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

p . Note that since p g , p likewise does not divide g k for any positive integer k . So, none
of the integers g , g

2 , . . . , g p 1 are congruent to 0 modulo p . Now, suppose
g i

g j (mod p )
for some positive integers i and j , where 0 < i ≤ j < p . By proposition 38, we then have i
j (mod | g |). But since i and j are both no greater than | g | = p 1 (recall that g is a genera-
tor), we must have i = j . Thus, no two members of g , g

2 , . . . , g p 1 are congruent modulo p ,
and so these integers must simply be a permutation of the positive integers not exceeding
p 1.

It is important to be able to find generators, since the discrete logarithm problem is most
intractable when generators are used as the base. Note that proposition 39 says that when
we have g x b (mod p ) for prime p and generator g , the solution (when it exists) is unique,
and, it turns out, harder to find.

PROPOSITION 40

If | b | p = t and u is a positive integer, then | b u | p = t /( t , u ).

Let s = | b u |, v = ( t , u ), t = tv for some integer t

Proof. , and u = uv for some integer u .

By proposition 7 we have

( t , u ) = 1.

Thus, we have

( b u ) t = ( b uv ) t / v = ( b t ) u

1 (mod p )

since | b | = t . Then, by proposition 37, s | t . But since

( b u ) s = b us 1 (mod p )
we have t | us , which is equivalent to tv | uvs . Thus we derive the fact that t

| us , and since t

and u are relatively prime, we have t | s by proposition 13. Now, since s | t , and since t | s ,

we have
| b u | = s = t = t /( t , u ).

We will now prove that if a prime p has a generator, then it has many generators. This is
important, since if there are too few generators (or none at all) to choose from when pick-
ing a generator for a cipher, one may be hard (or impossible) to find.

PROPOSITION 41 Let r be the number of positive integers not exceeding p 1 which
are relatively prime to p 1. Then, if the prime p has a generator, it has r of them.

Proof. Let g be a generator modulo p . By proposition 40, we know that

| g u | p = | g | p /( u , | g | p ) = ( p 1)/( u , p 1)
for any positive integer u . Furthermore, from the previous equation, we can say that
g u is a generator modulo p iff | g u | p = p

1 iff u and p 1 are relatively prime. ( * )