Number Theory - Elliptic Curves: Number Theory and Cryptography - page 468

Appendix A

Number Theory

Basic results

Let n be a positive integer and let Z n be the set of integers mod n .Itisa
group with respect to addition. We can represent the elements of Z n by the
numbers 0 , 1 , 2 ,...,n− 1. Let

Z n = {a | 1 ≤ a ≤ n, gcd( a, n )=1 }.

Then Z n is a group with respect to multiplication mod n .
Let a ∈ Z n .The order of a mod n is the smallest integer k> 0 such that

a k ≡ 1(mod n ). The order of a mod n divides φ ( n ), where φ is the Euler

φ -function.
Let p be a prime and let a ∈ Z p . The order of a mod p divides p − 1. A
primitive root mod p is an integer g such that the order of g mod p equals
p − 1. If g is a primitive root mod p , then every integer is congruent mod p
to0ortoapowerof g . For example, 3 is a primitive root mod 7 and

{ 1 , 3 , 9 , 27 , 81 , 243 }≡{ 1 , 3 , 2 , 6 , 4 , 5 } (mod 7) .

There are φ ( p− 1) primitive roots mod p . In particular, a primitive root mod
p always exists, so Z p is a cyclic group.
There is an easy criterion for deciding whether g is a primitive root mod
p , assuming we know the factorization of p − 1: If g ( p− 1) /q ≡ 1(mod p )for

all primes q|p − 1, then g is a primitive root mod p . This can be proved by
noting that if g is not a primitive root, then its order is a proper divisor of
p 1) /q for some prime q .

One way to find a primitive root for p , assuming the factorization of p − 1
is known, is simply to test the numbers 2, 3, 5, 6, ... successively until a
primitive root is found. Since there are many primitive roots, one should be
found fairly quickly in most cases.
A very useful result in number theory is the following.

− 1, hence divides ( p −