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:

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 p^m. As we have shown above, addition and multiplication modulo a prime number p form a finite field. The order of the field is p¹. However, modulo arithmetic on its own will not let us to construct a finite field with order of p^m for m > 1. For example, 2³ = 8, and we've already know (Z₈, +, *) is not a field. One way to construct a finite field with m >1 is using the polynomial basis. The field is constructed as a set of p^m polynomials along with two polynomial operations.

Here a polynomial f(x) is a mathematical expression in the form a_nxⁿ + a_n-1x^n-1 + ... + a₀. The highest exponent of x is the degree of the polynomial. For example, the degree of x⁵ + 3x³ + 4 is 5. In a polynomial, a_n, a_n-1, ... , a₀ are called coefficients. If in a polynomial, the coefficients a_n, a_n-1, ... , a₁ are all 0, or in other words, the polynomial is in the form of a₀, we call this polynomial a constant. We can add, subtract polynomials by combine the terms in the polynomials with the same powers. For example:

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:

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

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

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):

Similar to integers, you can do modular arithmetic with polynomials over a field. Now the operands and modulus are polynomials. Let f(x)= a_nxⁿ + a_n-1x^n-1 + ... + a₀ and g(x)= b_mx^m + b_m-1x^m-1 + ... + b₀ be two polynomials over a field F, then there is a unique polynomial r(x) of degree smaller than m and another unique polynomial h(x), both over F, such that f(x) = h(x)*g(x)+r(x). The polynomial r(x) is called the remainder of f(x) modulo g(x). For polynomials a(x), b(x) and g(x) which are over the same field, we say a(x) is congruent to b(x) modulo g(x) written a(x) ≡ b(x) mod g(x), if m(x) divides a(x)-b(x). For example (all polynomials are over GF(3)):

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²+x⁴= x⁴+2x², you reduce this result by dividing by x²-1:

The remainder 3 is then reduced modulo 3: 3 ≡ 0 mod 3. So the final result is 2x²+x⁴ ≡ 0 mod (x²-1).

Useful Links