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

Since x is a quadratic residue, we know that x p − 1

mod p = 1. This shows that y is a

2

root of x .

6.4 Finite Fields

Finite fields are useful in communication systems, and in cryptography in particular. In
addition to all Z p fields, we have other finite fields. We give without proof the following
theorem which characterizes the finite fields. 4

Theorem 6.7. We have the following results.

1. The cardinality of any finite field is a prime power p k .
2. For any prime power p k , there exists a finite field of cardinality p k . p is called
the characteristic of the field.
3. Two finite fields of same cardinality are isomorphic, so the finite field of car-
dinality p k is essentially unique. We denote it by GF( p k ) as Galois field of
cardinality p k .
4. GF( p k ) is isomorphic to a subfield of GF( p k × ) .
5. GF( p k ) can be defined as the quotient of the ring Z p [ x ] of polynomials with
coefficients in Z p by a principal ideal spanned by an irreducible polynomial of
degree k: Z p [ x ]

/ ( P ( x )) .

The last property suggests a way to represent finite fields: in order to define GF( p k ),
we first find an irreducible polynomial P ( x )ofdegree k in Z p [ x ]. 5 Then we repre-
sent an element of GF( p k ) as a polynomial in Z p [ x ] of degree at most k 1. Ad-

ditions are then performed as regular additions modulo p . Multiplications are per-
formed modulo P ( x ) and modulo p . Then all algorithms of this section generalize to
GF( p k ).

−

2. We must get
an irreducible polynomial of degree 2 in Z 2 [x]. We have only four polynomials of
degree 2:

As an example, let us consider GF(4) where p = 2 and k =

x 2

which is equal to x × x

x 2

+ 1 which is equal to ( x + 1) × ( x + 1) (remember that 1 + 1 = 0in Z 2 )

x 2

+ x which is equal to x × ( x + 1)

x 2

+ x + 1 which is irreducible.

4

For a more complete treatment on finite fields, we suggest the textbook by Lidl and Niederreiter (Ref. [117]).

5

Picking irreducible polynomials is quite easy. We can for instance pick random polynomials and check
irreducibility. Factorization of polynomials is actually easily feasible, so instead of making irreducibility
tests, we can directly try to factorize. More elaborate ways are also possible. They can be found in any
textbook on finite fields.