# Discrete Mathematics/Finite fields
## Introduction

Recall from the previous section that we considered the case where F[x]/<m(x)> analogous to modular arithmetic but with polynomials, and that when we are looking at numbers modulo n, we have a field iff Z$_n$ is a field if n is prime.
Can we say something similar about F[x]/<m(x)>? Indeed, if m(x) is irreducible then F[x]/<m(x)> is a field.
This section deals with these kinds of fields, known as a finite field.

## Definitions

We have the object F[x]/<m(x)> where this is the set of polynomials in F[x] are divided by the polynomial m(x).
Of the elements in F[x]/<m(x)> we can easily define addition, subtraction, multiplication, division and so on normally but with a reduction modulo m(x) to get the desired remainder.
We have that F[x]/<m(x)> is a commutative ring with identity, and if m(x) is irreducible then F[x]/<m(x)> is a field.
If m(x) has degree n, then
    $\mathbf {F} [x]/\langle m(x)\rangle =\{a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+\dots +a_{0}x^{0}|a_{i}\in \mathbf {F} \}$
If F is Z$_p$ (so p is prime) then $|\mathbf {F} [x]/\langle m(x)\rangle |=p^{n}$

## Properties

Now remember with complex numbers C, we have "invented" the symbol i to stand for the root of the solution x$^2$+1=0. In fact, we have C=R[x]/<x$^2$+1>.
When we have a general finite field, we can do this also. We write this often as F[x]/<m(x)>=F(α) where α is "the root of" m(x) - we define α to be the root of m(x).
F(α) in fact is the smallest field which contains F and α.

## Finite field theorems

We have a number of theorems associated with finite fields.
* If F is a finite field, |F|=q, then q=p$^k$ for some k $\geq$ 1 and p prime.
* There then is a monic irreducible polynomial m(x) with degree k such that F=Z$_p$[x]/<m(x)>=Z$_p$(α) with α a root of m(x) over Z$_p$
* There is an element γ∈F such that the order (the least element n such that γ$^n$=1) of γ is q-1, so γ is primitive in F, and we can generate elements of F (not zero) from powers of γ, i.e. F={0, γ$^0$=1, γ$^1$, ..., γ$^{q-2}$, γ$^{q-1}$=1}
* F is a vector space with dimension k over Z$_p$. It has basis {1, α, α$^2$,...,α$^{n-1}$} where n is the degree of m(x), so we have F={a$_{n-1}$α$^{n-1}$+...+a$_0$α$^0$|a$_i$∈F}
* If a∈F, a+...+a p times (pa) is 0.
* If m$_2$(x) is any other irreducible polynomial of degree k over Z$_p$ then F is isomorphic (meaning basically equal to, except for a change in symbols) to Z$_p$/<m$_2$(x)> - so all ways of writing this field are basically the same. So there is essentially one field of size q=p$^k$ and we denote it GF(p$^k$) (GF meaning Galois Field).

## Some examples

Let's look at a few examples that go through these ideas.

### The complex numbers

Complex numbers, briefly, are numbers in the form
    $a+bi$
where i is the solution to the equation x$^2$+1=0
These numbers in fact form a field, however it is not a finite field.
Take m(x)=x$^2$+1, with the field F being R. Then we can form the complex numbers as F/<m(x)>. Now F/<m(x)> = { a+bx | a, b ∈ R} because the remainders must be of degree less than m(x) - which is 2.
So then (a+bx)(c+dx)=ac+bdx$^2$+(ad+bc)x.
But remember that we are working in F/<m(x)>. So x$^2$ modulo x$^2$+1, can be written as (x$^2$+1)-1=-1, and substituting -1 above yields a rather familiar expression.
If we let the symbol i to be the "root of x$^2$+1", then i$^2$+1=0 and i$^2$=-1. The rest of the field axioms follow from here. We can then say the complex numbers C=R/<x$^2$+1>=R(i).

### The Z$_p$ case

We can still do this for some field in general. Let's take Z$_3$ for example, and pick m(x)=x$^2$+x+2. m(x) is irreducible - m(0)=2, m(1)=4=1, m(2)=4+2+2=8=2.
So Z$_3$/<x$^2$+x+2> is a finite field. Assume α is a root of m(x). Then Z$_3$(α) = { a+bα|a, b ∈ Z$_3$}. Since Z$_3$/<x$^2$+x+2> is finite, we can list out all its elements. We have the constant terms, then the α terms, then the α+constant terms, and so on. We have {0, 1, 2, α, α+1, α+2, 2α, 2α+1, 2α+2}.
Now we have α$^2$+α+2=0, then
    α$^2$=-α-2
    α$^2$=2α-2=2α+1
(Recall the coefficients are in Z$_3$! We are working in Z$_3$/<m(x)>)
We can verify multiplication works mod m(x) - for example
    (1+2α)(2+α) = 2 + α+4α+2α$^2$
Reducing coefficients normally mod 3 we get
    (1+2α)(2+α) = 2 + 2α + 2α$^2$
Now using the formula above for α$^2$
    (1+2α)(2+α)
       = 2 + 2α + 2(2α+1)
       = 2 + 2α+4α+2
       = 2 + 6α+2
       = 2 + 2 = 4 = 1
Verify for yourself that multiplication and other operations work too.

## Primitive elements

Recall from Modular arithmetic that the order of a number a modulo n, in a field, is the least power such that a$^{k-1}$=1 in Z$_n$, with k the size of this field. Since the order is defined over a field, this leads us to consider whether we have primitive elements in F[x]/<m(x)> - which we do. If we have F(α), just like in Z$_n$, α is primitive iff the order of α is q-1 where q is the number of elements in F[x]/<m(x)>.
Let's take Z$_2$/<x$^2$+x+1>. Is α (root of x$^2$+x+1) primitive?
First, if α is a root of x$^2$+x+1,
    α$^2$+α+1=0
    α$^2$=-α-1=α+1
Now, let us calculate powers of α
    1, α
    α$^2$=α+1
    α$^3$=α(α$^2$)=α(α+1)=α$^2$+α=(α+1)+α=1
Recall that the size of this field is 4 (the n in Z$_n$, in this case, 2, raised to the power of the degree of the polynomial, in this case 2). Now we have α$^3$=α$^{4-1}$=1, and α is primitive.
We generally want to look at powers of α in F(α), to see whether they are primitive, since we already know about the orders of the constants in F(α) - which we've looked at in Modular arithmetic.