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

Now, from proposition 39 we know that the sequence

2 , . . . , g p 1

g , g

is simply a permutation of 1, 2, . . . , p 1. Since there are exactly r integers in the first set

that are relatively prime to p 1, there are exactly r integers in the former sequence of the

form g i where i is relatively prime to p 1. But, from the previous development ( * ), these

are exactly the generators modulo p .

This tells us that when a prime has a generator, it has quite a few, since there are always
many positive integers smaller than p which are relatively prime to p 1.

E XAMPLE .

5 2 , any positive integer
smaller than 100 not having a 2 or a 5 in its factorization will be relatively prime to 100. There
are clearly many such integers.

Consider the prime p = 101; since p 1 = 100 = 2 2

Note that proposition 41 does not tell us that every prime has a generator; it only says
that if it has a generator, it has a certain number of them. We need this fact, but will not prove
it.

PROPOSITION 42 Every prime has a generator.
Proposition 41 also says that if we find a generator g modulo p , we can find another by
simply calculating the lnr of g i modulo p for some i relatively prime to p 1. But how do
we find a generator in the first place? This isn't difficult to do in practice, since we will
choose our primes carefully. For example, if prime p is such that p 1 consists entirely of
small factors, such a prime p is susceptible to some discrete logarithm finding algorithms
(like Pohlig-Hellman). If we choose p so that p 1 has at least one large prime factor, we
call it a safe prime.
A solution is to choose primes of the form p = 2 Rt + 1 where t is prime, and R is a rela-
tively small positive integer. We first select integers t at random, and subject them to pri-
mality testing, until a particular value of t passes. We then select small values of R (say, ≤
1 billion) at random and submit p = 2 Rt +1 to primality testing, until p passes with some value
of R . Since R is small, it can be easily factored, and since p 1 = 2 Rt , the factorization of
p 1 is known. Thus, we present a method of finding generators.

13.3 GENERATOR SELECTION

Suppose p is prime, and p 1 e 1

p 2 e 2 p n e n is the prime factorization of p

... 1. To find a

generator g modulo p , do the following:

1. Choose a random integer x between 2 and p 2.

2. For i = 1 to n do

a) Compute z = p / p i