Next: Finite Field Elements and Up: Finite Fields Previous: Finite Fields   Contents

## Finite Fields

Finite Fields sets of elements with multiplication and addition ''



Denote
, where :

is a prime

is a positive integer

has  elements


For n=1, fields are of the form

multiplication and addition are usual operations, except multiples of p should be left out of the set (modulo p).

Ex

We use the sign because the result is modulo p. That means that we are dividing the product by and the answer is the remainder of that division. All of the multiplication in the example is mod 5 because .

Multiplicative Inverse - for every non- zero element, ,
there is a multiplicative inverse, .
All of the operations below are (mod 5).

Having a prime {0, 1, 2, 3...p-1}
guarantees a multiplicative inverse.
No Inverse Example " ", 6 is not prime.

{0, 1, 2, 3, 4, 5}
-Is there an inverse of 2?
A zero divisor is not what we want because the product of two positive numbers should not be 0

We tested the product of 2 and every number in the field, but we never got a product of 1. This means that there is no multiplicative inverse.

( elements)

Goal filed with 8 elements.

cannot do modulo

The reason cannot have those elements is because not all elements will have multiplicative inverses.

Explanation:

,

In this field 3 is a zero divisor = bad"

Motivating Example
Construction of omplex numbers from eal numbers
The field of complex numbers is denoted and

This field has the multiplication rule:
Another way is to look at the polynomials in , denoted , modulo the quadratic .

which is the same as the multiplication rule

 0

Example for the Goal : Figure out , the field with 4 elements.
Note: sits inside of



- 		 look at polynomials in

in fact look for just quadratic polynomials,

with the condition:

Condition- 		  has no zeros in
.


This is a list of all the quadratic polynomials over = {0, 1}''

 f(x) f(0) f(1) 0 1 1 0 0 0 1 1

This shows that has no zeros, so use this to construct . We did the same thing finding from . We looked at which has no zeros over .
construct =

a+c= 0 c= 0
b+d= b d= 0
0 is still the additive identity.
(a+bx) has the additive inverse -a-bx.
Multiplication is usual multiplication os polynomials except need to use .

this seems to be a problem because only has linear polynomials but we ended up with a quadratic one.
We fix" this using
replacement rule, anytime you see , replace with because

 0

When constructing the elements of remember had multiplication modulo p = 2, so has polynomial multiplication modulo . Also sits inside of as the ''constant'' polynomials.
We end up with the multiplication table of :

Remember when making these tables that each element will only show up once in any column or row. This is because we want to show that each element has a multiplicative inverse, and that there are no zero divisors.
If we name and , then the table will look like this:
 0 1 0 0 0 0 0 1 0 1 0 1 0 1

As a vector space,
To find the multiplication table we need a monic-quadratic that has no zeros in
A monic-quadratic will have a coefficient of 1 on the highest degree term.
Try , f(0)= 1, f(1)=2 f(2)=2 (no zeros!)
Note: The constant term must to be non zero, because otherwise 0 is a zero.
Also note that we only need one polynomial that works.

Multiplication table for ,
 0 1 2 x x+1 x+2 2x 2x+1 2x+2 0 0 0 0 0 0 0 0 0 0 1 0 1 2 x x+1 x+2 2x 2x+1 2x+2 2 0 2 1 2x 2x+2 2x+1 x x+2 x+1 x 0 x 2x 2 x+2 2x+2 1 x+1 2x+1 x+1 0 x+1 2x+2 x+2 2x 1 2x+1 2 x x+2 0 x+2 2x+1 2x+2 1 x x+1 2x 2 2x 0 2x x 1 2x+1 x+1 2 2x+2 x+2 2x+1 0 2x+1 x+2 x+1 2 2x 2x+2 x 1 2x+2 0 2x+2 x+1 2x+1 x 2 x+2 1 2x

Construct out of .
We need a monic-cubic polynomial with no zeros/roots in . The polynomial will be of the form , but with no zeros.
Try a=1, b=0. , has no zeros over . .
( as vector spaces)

Multiplication Table of (0,1 columns and rows excluded)
 x x+1 x 1 x+1 1 x 1 x+1 x x x+1 1 1 x x+1 1 x

Sample multiplication

Next: Finite Field Elements and Up: Finite Fields Previous: Finite Fields   Contents
Frederick Leitner 2004-09-01