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²+1=0. In fact, we have C=R[x]/<x²+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.

1. If F is a finite field, |F|=q, then q=p^k for some k $\geq$ 1 and p prime.
2. 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
3. There is an element γ∈F such that the order (the least element n such that γⁿ=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, γ⁰=1, γ¹, ..., γ^q-2, γ^q-1=1}
4. F is a vector space with dimension k over Z_p. It has basis {1, α, α²,...,α^n-1} where n is the degree of m(x), so we have F={a_n-1α^n-1+...+a₀α⁰|a_i∈F}
5. If a∈F, a+...+a p times (pa) is 0.
6. If m₂(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₂(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²+1=0

These numbers in fact form a field, however it is not a finite field.

Take m(x)=x²+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²+(ad+bc)x.

But remember that we are working in F/<m(x)>. So x² modulo x²+1, can be written as (x²+1)-1=-1, and substituting -1 above yields a rather familiar expression.

If we let the symbol i to be the "root of x²+1", then i²+1=0 and i²=-1. The rest of the field axioms follow from here. We can then say the complex numbers C=R/<x²+1>=R(i).

The Z_p case

We can still do this for some field in general. Let's take Z₃ for example, and pick m(x)=x²+x+2. m(x) is irreducible - m(0)=2, m(1)=4=1, m(2)=4+2+2=8=2.

So Z₃/<x²+x+2> is a finite field. Assume α is a root of m(x). Then Z₃(α) = { a+bα|a, b ∈ Z₃}. Since Z₃/<x²+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=0, then

α²=-α-2

α²=2α-2=2α+1

(Recall the coefficients are in Z₃! We are working in Z₃/<m(x)>)

We can verify multiplication works mod m(x) - for example

(1+2α)(2+α) = 2 + α+4α+2α²

Reducing coefficients normally mod 3 we get

(1+2α)(2+α) = 2 + 2α + 2α²

Now using the formula above for α²

(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₂/<x²+x+1>. Is α (root of x²+x+1) primitive?

First, if α is a root of x²+x+1,

α²+α+1=0

α²=-α-1=α+1

Now, let us calculate powers of α

1, α

α²=α+1

α³=α(α²)=α(α+1)=α²+α=(α+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 α³=α^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.