# Discrete Mathematics/Finite fields

## IntroductionEdit

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**.

## DefinitionsEdit

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

If **F** is **Z**_{p} (so *p* is prime) then

## PropertiesEdit

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 theoremsEdit

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*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 examplesEdit

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

### The complex numbersEdit

Complex numbers, briefly, are numbers in the form

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} caseEdit

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 elementsEdit

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.