3.7 Primitive Roots – Introduction to Cryptography with Coding Theory, 3rd Edition

3.7 Primitive Roots

Consider the powers of 3(mod7):

313, 322, 336, 344, 355, 361.

Note that we obtain all the nonzero congruence classes mod 7 as powers of 3. This means that 3 is a primitive root mod 7 (the term multiplicative generator might be better but is not as common). Similarly, every nonzero congruence class mod 13 is a power of 2, so 2 is a primitive root mod 13. However, 331(mod13),  so the powers of 3 mod 13 repeat much more frequently:

313, 329, 331, 343, 359, 361, , 

so only 1, 3, 9 are powers of 3. Therefore, 3 is not a primitive root mod 13. The primitive roots mod 13 are 2, 6, 7, 11.

In general, when p is a prime, a primitive root mod p is a number whose powers yield every nonzero class mod p. It can be shown that there are ϕ(p1) primitive roots mod p. In particular, there is always at least one. In practice, it is not difficult to find one, at least if the factorization of p1 is known. See Exercise 54.

The following summarizes the main facts we need about primitive roots.

Proposition

Let α be a primitive root for the prime p.

  1. Let n be an integer. Then αn1(modp) if and only if n0(modp1).

  2. If j and k are integers, then αjαk(modp) if and only if jk(modp1).

  3. A number β is a primitive root mod p if and only if p1 is the smallest positive integer k such that βk1(modp).

Proof. If n0(modp1),  then n=(p1)m for some m. Therefore,

αn(αm)p11(modp)

by Fermat’s theorem. Conversely, suppose αn1(modp). We want to show that p1 divides n,  so we divide p1 into n and try to show that the remainder is 0. Write

n=(p1)q+r, with0r<p1

(this is just division with quotient q and remainder r). We have

1αn(αq)p1αr1αrαr(modp).

Suppose r>0. If we consider the powers α, α2,  of α(modp),  then we get back to 1 after r steps. Then

αr+1α, αr+2α2, 

so the powers of α(modp) yield only the r numbers α, α2, , 1. Since r<p1,  not every number mod p can be a power of α. This contradicts the assumption that α is a primitive root.

The only possibility that remains is that r=0. This means that n=(p1)q,  so p1 divides n. This proves part (1).

For part (2), assume that jk (if not, switch j and k). Suppose that αjαk(modp). Dividing both sides by αk yields αjk1(modp). By part (1), jk0(modp1),  so jk(modp1). Conversely, if jk(modp1),  then jk0(modp1),  so αjk1(modp),  again by part (1). Multiplying by αk yields the result.

For part (3), if β is a primitive root, then part (1) says that any integer k with βk1modp must be a multiple of p1,  so k=p1 is the smallest. Conversely, suppose k=p1 is the smallest. Look at the numbers 1, β, β2, , βp2(modp). If two are congruent mod p,  say βiβj with 0i<jp2,  then βji1(modp) (note: βp11(modp) implies that β0(modp),  so we can divide by β). Since 0<ji<p1,  this contradicts the assumption that k=p1 is smallest. Therefore, the numbers 1, β, β2, , βp2 must be distinct mod p. Since there are p1 numbers on this list and there are p1 numbers 1, 2, 3, , p1 mod p,  the two lists must be the same, up to order. Therefore, each number on the list 1, 2, 3, , p1 is congruent to a power of β,  so β is a primitive root mod p.

Warning: α is a primitive root mod p if and only if p1 is the smallest positive n such that αn1(modp). If you want to prove that α is a primitive root, it does not suffice to prove that αp11(modp). After all, Fermat’s theorem says that every α satisfies this, as long as α0(modp). To prove that α is a primitive root, you must show that p1 is the smallest positive exponent k such that αk1.