Appendix A: Mathematical Facts - Codes: The Guide to Secrecy from Ancient to Modern Times - page 479

Proof . See [169, Proposition 4.3, page 161].

✷

Definition A.24 ( Primitive Roots)
If m ∈ Z , n ∈ N and

ord n ( m )= φ ( n ) ,
then m is called a primitive root modulo n . In other words, m is a primitive
root if it belongs to the exponent φ ( n ) modulo n .

Theorem A.15 ( Primitive Root Theorem )
An integer n> 1 has a primitive root if and only if n is of the form 2 a p b
where p is an odd prime, 0

≤ a ≤ 1 , and b ≥ 0 or n =4 . Also, if m has a

primitive root, then it has φ ( φ ( n )) of them.

Proof . See [169, Theorem 4.10, page 165].

✷

Definition A.25 ( Index )
Let n ∈ N with primitive root m , and b ∈ N with gcd( b,n )=1 . Then for

m e (mod n ) holds. This
unique value e modulo φ ( n ) is the index of b to the base m modulo n , denoted
by ind m ( b ) .

exactly one of the values e ∈{ 0 , 1 ,...,φ ( n ) − 1 } , b ≡

Definition A.25 gives rise to an arithmetic of its own, the index calculus . The
following are some of the properties.

Theorem A.16 ( Index Calculus )
If n ∈ N and m is a primitive root modulo n , then for any c,d ∈ Z each of

the following holds.

ind m ( cd ) ind m ( c ) + ind m ( d ) (mod φ ( n )) .

≡

(1)

, ind m ( c t ) ind m ( c ) (mod φ ( n )) . (2) For any t ∈ N ≡ t ·

ind m (1) = 0 . (3)

ind m ( m )=1 . (4)

ind m ( (5) − 1) = φ ( n ) / 2 for n> 2 .

ind m ( n ind m ( φ ( n ) / 2 + ind m ( c ) (mod φ ( n )) . (6) − c ) ≡ − c ) ≡

Proof . See [169, Theorem 4.14, page 166].

✷

Proposition A.4 ( Primitive Roots and Primality )

(1) If m is a primitive root modulo an odd prime p , then for any prime q
dividing ( p

1) , m ( p − 1) /q

− ≡ 1 (mod p ) .