Algorithmic Algebra - A Classical Introduction to Cryptography: Applications for Communications Security - page 168

In Theorem 6.3 we saw that a ring element x of Z n is invertible if and only if the
gcd of x and n is 1. When n is prime, all nonzero elements of Z n fulfill this property.
But if n is composite, we may have a nontrivial factor x , and for all integers y we know
that xy mod n is a multiple of x , so it cannot be 1. This means that Z n is a field if and
only if n is a prime integer. In the following, we let p denote a prime integer and focus
on the field Z p .

It is important to emphasize that Z p is a finite field : we have a finite number of
elements in it. This is not the case for classical fields: the field of real numbers R , the
field of complex numbers C , the field of rational numbers Q , etc.

Here are a few properties allowing to get familiar with Z p .
Z p ={

1 ,..., p − 1 } since Z p ={ 0 , 1 ,..., p − 1 } and zero is the only nonin-

vertible element;
ϕ

1 since Z p contains p ( p ) = p − − 1 elements;

for any x

Z p ,wehave x p − 1

∈ ≡ 1 (mod p ) since the order of x is a factor of the

1of Z p .

order p −

We have the following important result.

Theorem 6.5. Let p be a prime number. Z p is a cyclic group with ϕ ( p − 1) generators.

We recall that a cyclic group is a group which has at least one generator , namely an
element g such that all group elements are powers of g , i.e. Z p ={ g 2 g p − 2 .

Assuming that Z p is cyclic, it is fairly easy to prove that the number of possible
generators is actually

1 , g , ,..., }

ϕ ( p − 1). For this we can pick a generator g and find conditions

2 for g i mod p to be a generator of Z p . It is a generator if and only
if there exists a j such that g ij mod p

on i = 1 ,..., p −

=

g : it is necessary because a generator must
generate g , and it is sufficient because if it generates g , we know that we can generate
all elements from g only. Since the exponents of g “live” in Z p − 1 , g ij mod p

=

g is

equivalent to ij ≡ 1 (mod p − 1). Hence such a j exists if and only if i is invertible

modulo p − 1. We already know that we have exactly ϕ ( p − 1) invertible elements

modulo p − 1, which completes the proof.

6.3.2 Quadratic Residues

Z p when e

In Theorem 6.3 we saw how to extract e -th roots modulo p of an element x ∈

1: we just have to raise x to the power e − 1 is invertible modulo ϕ ( p ) = p − mod p − 1.

How can we proceed when e is not invertible modulo p − 1? In particular, how can we

1iseven? 3 As for real num-
bers, square roots do not always exist (e.g. for negative numbers), and when they do, they
come in couples which are the opposite of each other. In finite fields, we call quadratic
residues the elements which can be written as the square of some other element.

proceed with e = 2 which will never be invertible since p −

3

We omit the p = 2 case here which is trivial.