Corollary 2.5.2

Corollary 2.5.2 Suppose p and q are prime, and p =2q + 1. Suppose g Є Z*_p is not a

primitive element, and g ≠±1(mod p). Then (-g) is a primitive element.

This means that we have an efficient deterministic algorithm to find a primitive element

for when p and (p - 1)/2 are both prime.

It is not so easy to verify that elements are primitive if the factorization of p – 1 is

not known. For this reason, the designer of a cryptosystem will often construct p in such

a way that the factorization of p - 1 is known. For example, it is often desirable to

implement a cryptosystem in Z_p, where p =2q + 1 and p and q are both prime. One

reason why this might be done is that it ensures that the system will not be vulnerable

to a Pohlig-Hellman attack on the discrete logarithm problem. To find such a p, the

designer of the system will choose a random odd value q, and test both p and p =2q +1

for primality using one of the probablistic primality tests. If either of p or q is found

to be composite, then a new random value of q is chosen and the process is repeated.

As another example, several protocols are implemented in Z_p where p - 1 has a prime

divisor q of a specified size. A convenient realization of such a system would be to take

p =2qr + 1, where p, q and r are all primes. if q is to be a 160-bit prime and p is to be a

512-bit prime, then r will be a prime of approximately 352 bits. Here, the designer of the

system would begin by choosing random values q and r of the appropriate size, and then

define p =2qr + 1. The three integers p, q and r will all be tested for primality using a

probabilistic primality testing algorithm.