2.5 Finding Primitive Elements in Z_p

2.5 Finding Primitive Elements in Z_p

In many public key distribution protocols based on Diffie-Hellman, it is necessary to find

a primitive element of g Є Zp, where p is prime. This is not too difficult to do if the

factorization of p - 1 is known. For the remainder of this section, let us assume that the

factorization of p – 1 is

p - 1 =p_1^e_1…p_k^e_k

where p_1,p_2, … ,p_k are distinct primes.

First, we present a lemma that provides a metho d of determining if a given element

g Є Z*_p is primitive.