Lemma 2.5.1

Lemma 2.5.1 Suppose p is prime, and the factorization of p - 1 is as given above. Then

g Є Z*_p is a primitive.

g^[(p-1)/p_j] ≠ 1(mod p)

for 1 ≤ j ≤ k.

Proof. Let d denote the order of g. We know that d is a divisor of p - 1 and g is primitive if and only if d = p - 1.

First, suppose that g^[(p-1)/p_j]≡ 1(mod p) for some j. Then clearly d ≤ (p - 1)/p_j, so

certainly d ≠ p - 1.

Conversely, suppose that g^[(p-1)/p_j] ≠ 1 (mod p) for 1 ≤ j ≤ k. Suppose that d ≠ p - 1.

Since d is a divisor of p - 1 and d1 ≤ j ≤ k) such that

P_j is a divisor of (p - 1)/d. But this implies that d is a divisor of (p - 1)/p_j. Hence, it

follows that

g^[(p-1)/p_j]≡ gd≡ 1(mod p),

which is a contradiction. This proves that d = p - 1, as desired.

Now, given that we have an efficient method of detemining if a given element g is primitive, how do we go about finding a primitive element? This can be done quite easily by means of Las Vegas algorithm, by choosing random values for g and testing them, until a primitve element is found. The effectiveness of this approach depends on the probability that a random element g Є Z*_p is primitive. Altogether, there are exactly φ(p -1) primitive elements in Z*_p, so the probability that a random element g is a primitive element is φ (p - 1)/(p - 1).

One special case of interest is when p =2q + 1, where q is prime. In this case, the following corollary is obtained.