Discrete Mathematics/Finite fields

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Introduction[edit | edit source]

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 Zn 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[edit | edit source]

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 Zp (so p is prime) then

Properties[edit | edit source]

Now remember with complex numbers C, we have "invented" the symbol i to stand for the root of the solution x2+1=0. In fact, we have C=R[x]/<x2+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[edit | edit source]

We have a number of theorems associated with finite fields.

  1. If F is a finite field, |F|=q, then q=pk for some k 1 and p prime.
  2. There then is a monic irreducible polynomial m(x) with degree k such that F=Zp[x]/<m(x)>=Zp(α) with α a root of m(x) over Zp
  3. 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}
  4. F is a vector space with dimension k over Zp. It has basis {1, α, α2,...,αn-1} where n is the degree of m(x), so we have F={an-1αn-1+...+a0α0|aiF}
  5. If a∈F, a+...+a p times (pa) is 0.
  6. If m2(x) is any other irreducible polynomial of degree k over Zp then F is isomorphic (meaning basically equal to, except for a change in symbols) to Zp/<m2(x)> - so all ways of writing this field are basically the same. So there is essentially one field of size q=pk and we denote it GF(pk) (GF meaning Galois Field).

Some examples[edit | edit source]

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

The complex numbers[edit | edit source]

Complex numbers, briefly, are numbers in the form

where i is the solution to the equation x2+1=0

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

Take m(x)=x2+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, bR} because the remainders must be of degree less than m(x) - which is 2.

So then (a+bx)(c+dx)=ac+bdx2+(ad+bc)x.

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

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

The Zp case[edit | edit source]

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

So Z3/<x2+x+2> is a finite field. Assume α is a root of m(x). Then Z3(α) = { a+bα|a, bZ3}. Since Z3/<x2+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 Z3! We are working in Z3/<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[edit | edit source]

Recall from Modular arithmetic that the order of a number a modulo n, in a field, is the least power such that ak-1=1 in Zn, 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 Zn, α is primitive iff the order of α is q-1 where q is the number of elements in F[x]/<m(x)>.

Let's take Z2/<x2+x+1>. Is α (root of x2+x+1) primitive?

First, if α is a root of x2+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 Zn, in this case, 2, raised to the power of the degree of the polynomial, in this case 2). Now we have α34-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.