Sometimes, a finite field is also called a Galois Field. It is so named in honour of Évariste Galois, a French mathematician. Galois is the first one who established the following fundamental theorem on the existence of finite fields:

An order-

nfinite field exists if and only ifn = pfor some prime^{m}p(pis called the characteristic of this finite field) and some positive integerm.

In fact, an order-*n* finite field is unique
(up to isomorphism). All finite fields of the same order are
structurally identical. We usually use
*GF*(*p ^{m}*)
to represent the finite field of order

Here a polynomial *f(x)* is a mathematical
expression in the form *a _{n}x^{n} +
a_{n-1}x^{n-1} + ... +
a_{0}*. The highest exponent of

Polynomial addition: (

)+(*x*^{5}+ 3x^{3}+ 4) =*6x*^{6}+ 4x^{3}*6x*^{6}+ x^{5}+ 7x^{3}+ 4

Polynomial subtraction: (

)-(*x*^{5}+ 3x^{3}+ 4) =*6x*^{6}+ 4x^{3}*-6x*^{6}+ x^{5}-x^{3}+ 4

We can also multiply two polynomials. The general rule is that each term in the first polynomial has to multiply each term in the second polynomial, then sum the resulted polynomials up. For example:

Polynomial multiplication: (

)*(*x*^{5}+ 3x^{3}+ 4) =*6x*^{6}+ 4x^{3}*6x*^{11}+ 18x^{9}+ 4x^{8}+ 36x^{6}+ 16x^{3}

We can also divide polynomials using long division. For example:

Polynomial division: (6x

^{11}+ 18x^{9}+ 4x^{8}+ 36x^{6}+ 16x^{3}) ÷ (x^{5}+ 3x^{3}+ 4) =*6x*^{6}+ 4x^{3}

But in many cases the divisors cannot divide the dividends, which means you will have remainders. For example:

Polynomial division with remainder: (3x

^{6}+ 7x^{4}+ 4x^{3}+ 5) ÷ (x^{4}+ 3x^{3}+ 4) =3x^{2}- 9x + 34 with remainder -98x^{3}- 12x^{2}+ 26x -131

If a polynomial is divisible only by itself and constants, then we
call this polynomial an **irreducible
polynomial.** We will see later that irreducible polynomials
have properties similar to prime numbers.

If the coefficients are taken from a field
*F*, then we say it is a
**polynomial over F.** With polynomials
over field *GF*(*p*), you can add
and multiply polynomials just like you have always done but the
coefficients need to be reduced modulo *p*. For
example, compare the above results with polynomials over
*GF*(11):

(

)+(*x*^{5}+ 3x^{3}+ 4) =*6x*^{6}+ 4x^{3}*6x*^{6}+ x^{5}+ 7x^{3}+ 4(

)-(*x*^{5}+ 3x^{3}+ 4) =*6x*^{6}+ 4x^{3}*5x*^{6}+ x^{5}+10x^{3}+ 4(

)*(*x*^{5}+ 3x^{3}+ 4) =*6x*^{6}+ 4x^{3}*6x*^{11}+ 7x^{9}+ 4x^{8}+ 3x^{6}+ 5x^{3}(3x

^{6}+ 7x^{4}+ 4x^{3}+ 5) ÷ (x^{4}+ 3x^{3}+ 4) =3x^{2}+ 3x + 3 with remainder x^{3}+ 10x^{2}+ 4x +1

Similar to integers, you can do modular arithmetic with
polynomials over a field. Now the operands and modulus are polynomials.
Let *f*(*x*)=
*a _{n}x^{n} +
a_{n-1}x^{n-1} + ... +
a_{0}* and

2

*x*^{2}≡ 2 mod (*x*^{2}-1)*x*^{4}≡ 1 mod (*x*^{2}-1)*x*^{3}≡*x*mod (*x*^{2}-1)2

*x*^{2}+*x*^{4}≡ 0 mod (*x*^{2}-1)2

*x*^{2}**x*^{4}≡ 2 mod (*x*^{2}-1)2

*x*^{2}+*x*^{3}≡*x*+2 mod (*x*^{2}-1)

Always remember there are two moduli involved: a polynomial
modulus and an integer modulus. You need to reduce the result from the
polynomial operations by modulo the polynomial modulus and then reduce
the coefficients modulo the integer modulus. Take one of the above
examples: 2x^{2}+x^{4}=
x^{4}+2x^{2}, you reduce
this result by dividing by x^{2}-1:

The remainder 3 is then reduced modulo 3: 3 ≡ 0 mod 3. So the
final result is 2*x*^{2}+*x*^{4} ≡
0 mod (*x*^{2}-1).

**Useful Links**