next up previous contents
Next: Linear Codes Up: Spring 2004 Final Report Previous: Sentences as Numbers   Contents

Finite Fields $ \FF[p^n]$

Finite Fields ``sets of elements with multiplication and addition ''




  
Denote $ \FF[p^n]$, where :

$ p$ is a prime
$ n$ is a positive integer
$ \FF[p^n]$ has $ p^n$ elements
For n=1, fields are of the form

$ \FF[p] = \overbrace{\{0, 1, 2, 3, ... p-1\}}^{p-elements}$
multiplication and addition are usual operations, except multiples of p should be left out of the set (modulo p).


Ex

$ \FF[5]={0, 1, 2, 3, 4}$


$\displaystyle 2*2\equiv4$ $\displaystyle 1*3\equiv3$ $\displaystyle 4*0\equiv0$  
$\displaystyle 2*3\equiv6\equiv1$ $\displaystyle 3*5\equiv15\equiv0$ $\displaystyle 3*5\equiv3*0\equiv0$  
$\displaystyle 7+9\equiv2+4\equiv6\equiv1$      
       
$\displaystyle \underline{notice}$ $\displaystyle \underbrace{ x + 0 \equiv
0}_{\textrm{additive identity}}$ $\displaystyle \underbrace{x*1\equiv
x}_{\textrm{multiplicative identity}}$  

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


Multiplicative Inverse - for every non- zero element, $ x$,
there is a multiplicative inverse, $ x^{-1}$.
All of the operations below are (mod 5).
$ 1*1\equiv1\\
2*3\equiv1\\
3*2\equiv1\\
4*4\equiv1\\
\uparrow$ $ \uparrow\\
x$ $ x^{-1}$
Additive Identity -same as subtraction
$ 3+(-3)\equiv3+(-3+5)\equiv3+2\equiv0 \; ( mod 5)$
Having a prime {0, 1, 2, 3...p-1}
guarantees a multiplicative inverse.
No Inverse Example ``$ p-1=5$" ``$ p=6$", 6 is not prime.

{0, 1, 2, 3, 4, 5}
-Is there an inverse of 2?
$ 2*1\equiv2\\
2*2\equiv4\\
2*3\equiv6\equiv0 \leftarrow$A zero divisor is not what we want because the product of two positive numbers should not be 0
$ 2*4\equiv8\equiv2\\
2*5\equiv10\equiv4$
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.

$\displaystyle \hline$      

$ \FF[p^n]$ ($ p^n$ elements)

Goal $ \FF[2^3] = \FF[8] = $ filed with 8 elements.
$ \FF[p^n] \neq \{0, 1, 2, ... p^n-1\}$

cannot do modulo $ p^n$

The reason $ \FF[2^3]$ cannot have those elements is because not all elements will have multiplicative inverses.


Explanation:

$ p=3$ $ n=2$, $ \{0, 1, 2, \dots, 3^2-1=8\}$

In this field $ 3*3\equiv9\equiv0\Rightarrow$ 3 is a zero divisor = ``bad"

Motivating Example
Construction of $ \mathbb{C}$omplex numbers from $ \mathbb{R}$eal numbers
The field of complex numbers is denoted $ \mathbb{C}$ and
$ \mathbb{C}=\{a+bi\vert a,b \textrm{are real
numbers}\}=\{a+bi\vert a,b\epsilon\mathbb{R}\}$
This field has the multiplication rule: $ (a+bi)*(a'+b'i)=(aa'-bb')+i(ab'+a'b)$
Another way is to look at the polynomials in $ \mathbb{R}$, denoted $ \mathbb{R}[x]$, modulo the quadratic $ x^2+1$.
$ x^2+1=0$ $ x^2=-1$

$\displaystyle \mathbb{R}[x]$ $\displaystyle =$ $\displaystyle \{a+bx\vert a,b\epsilon\mathbb{R}\}$  
$\displaystyle (a+bx)*(a'b'x)$ $\displaystyle =$ $\displaystyle aa'+(a'b+b'a)x+bb'x^2$  
  $\displaystyle =$ $\displaystyle aa'+(a'b+b'a)x+(-1)bb'$  
  $\displaystyle =$ $\displaystyle (aa'-bb')+(a'b+b'a)$  

$ \uparrow$ which is the same as the multiplication rule


$\displaystyle x^2+1$ $\displaystyle =$ 0  
$\displaystyle x^2$ $\displaystyle =$ $\displaystyle -1$  
$\displaystyle x$ $\displaystyle =$ $\displaystyle \pm\sqrt{-1}=\pm i \leftarrow \textrm{imaginary number}$  


Example for the Goal : Figure out $ \FF[4]$, the field with 4 elements.
Note: $ \FF[2]$ sits inside of $ \FF[4]$



  
 Start with $ \FF[2]$- 		 look at polynomials in $ \FF[2]$

in fact look for just quadratic polynomials, $ q(x)$
with the condition:

Condition- $ q(x)$ has no zeros in $ \FF[2]$.
This is a list of all the quadratic polynomials ``over $ \FF[2]$ = {0, 1}''
$\displaystyle f(x)$ $\displaystyle =$ $\displaystyle 1x^2 + 0x + 0x^0 = x^2$  
$\displaystyle f(x)$ $\displaystyle =$ $\displaystyle 1x^2 + 0x + 1x^0 = x^2 + 1$  
$\displaystyle f(x)$ $\displaystyle =$ $\displaystyle 1x^2 + 1x + 0x^0 = x^2 + x$  
$\displaystyle f(x)$ $\displaystyle =$ $\displaystyle 1x^2 + 1x + 1x^0 = x^2 + x + 1$  

f(x) f(0) f(1)
$ x^2$ 0 1
$ x^2+1$ 1 0
$ x^2 + x$ 0 0
$ x^2+x+1$ 1 1

This shows that $ x^2+x+1$ has no zeros, so use this to construct $ \FF[4]$. We did the same thing finding $ \mathbb{C}$ from $ \mathbb{R}$. We looked at $ x^2+1$ which has no zeros over $ \mathbb{R}$.
construct $ \FF[4]= \{a+bx \vert a, b \epsilon \FF[2] \}$ =

$\displaystyle \left\{
\begin{tabular}{c} 0 +0x\\ 0+ 1x\\ 1+0x\\ 1+x\\ \end{tab...
...ight\} = \left\{ \begin{tabular}{c} 0\\ x\\ 1\\
1+x\\ \end{tabular} \right\} $

Addition on $ \FF[4]$ is addition of polynomials. $ (a+bx) + (c+dx)
= ( a+c) + x(b+d)$ What is the additive identity?
$ (a+bx) + (c+dx) =(a+bx)= ( a+c) + x(b+d)$
a+c= 0 c= 0
b+d= b d= 0
% latex2html id marker 2133
$ \therefore$ 0 is still the additive identity.
(a+bx) has the additive inverse -a-bx.
Multiplication is usual multiplication os polynomials except need to use $ x^2 + x + 1 = 0$.
$ (a+bx)*(c+dx)= ac=x(bc+ad)+ x^2(bd)$

$ \uparrow$ this seems to be a problem because $ \FF[4]$ only has linear polynomials but we ended up with a quadratic one.
We ``fix" this using $ x^2+x+1\equiv0$
$ x^2\equiv -x-1\equiv x+1$ $ \leftarrow$ replacement rule, anytime you see $ x^2$, replace with $ x + 1$ because

$\displaystyle x^2+x+1$ $\displaystyle \equiv$ 0  
$\displaystyle x^2$ $\displaystyle \equiv$ $\displaystyle -x-1$  
  $\displaystyle \equiv$ $\displaystyle x+1$  


When constructing the elements of $ \FF[2]$ remember had multiplication modulo p = 2, so $ \FF[4]$ has polynomial multiplication modulo $ x^2+x+1$. Also $ \FF[2]$ sits inside of $ \FF[4]$ as the ''constant'' polynomials.
We end up with the multiplication table of $ \FF[4]$:

$\displaystyle \begin{tabular}{c\vert\vert c\vert c\vert c\vert c}
& 0& 1& x& x...
...
1&0&1&x&x+1\\ \hline
x&0&x&x+1&1\\ \hline
x+1&0&x+1&1&x\\
\end{tabular}
$

$ \Rightarrow$ 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 $ x = \alpha$ and $ x+1 = \beta$, then the table will look like this:
  0 1 $ \alpha$ $ \beta$
0 0 0 0 0
1 0 1 $ \alpha$ $ \beta$
$ \alpha$ 0 $ \alpha$ $ \beta$ 1
$ \beta$ 0 $ \beta$ 1 $ \alpha$



As a vector space, $ \FF[9] = \FF[3^2] = \{a+bx \vert a, b \epsilon \FF[3]\}$
To find the multiplication table we need a monic-quadratic that has no zeros in $ \FF[3]$
A monic-quadratic will have a coefficient of 1 on the highest degree term.
Try $ 1x^2+0x+1$, 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 $ \FF[9]$, $ x^2+1=0$
  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 $ \FF[8]= \FF[2^3]$ out of $ \FF[2]$.
We need a monic-cubic polynomial with no zeros/roots in $ \FF[2]$. The polynomial will be of the form $ c(x)= x^3+ax^2+bx+1$, but with no zeros.
Try a=1, b=0. $ c(x)=x^3+x^2+1$, has no zeros over $ \FF[2]$. $ x^3=-x^2-1=x^2+1$.
$ \FF[8] = \{a+bx+cx^2 \vert a, b, c \epsilon\FF[2]\}$ ($ =\FF[2]^3$ as vector spaces)


Multiplication Table of $ \FF[8]$ (0,1 columns and rows excluded)
  x x+1 $ x^2$ $ x^2+1$ $ x^2 + x$ $ x^2+x+1$
x $ x^2$ $ x^2 + x$ $ x^2+1$ $ x^2+x+1$ 1 $ x + 1$
x+1 $ x^2 + x$ $ x^2+1$ 1 x $ x^2+x+1$ $ x^2$
$ x^2$ $ x^2+1$ 1 $ x^2+x+1$ x+1 x $ x^2 + x$
$ x^2+1$ $ x^2+x+1$ x x+1 $ x^2 + x$ $ x^2$ 1
$ x^2 + x$ 1 $ x^2+x+1$ x $ x^2$ x+1 $ x^2+1$
$ x^2+x+1$ $ x + 1$ $ x^2$ $ x^2 + x$ 1 $ x^2+1$ x


Sample multiplication

$\displaystyle (x+1)(x^2+x)$ $\displaystyle \equiv$ $\displaystyle x^3+x^2+x^2+x$  
  $\displaystyle \equiv$ $\displaystyle x^3+2x^2+x$  
  $\displaystyle \equiv$ $\displaystyle x^3+x$  
  $\displaystyle \equiv$ $\displaystyle (x^2+1)+x$  
  $\displaystyle \equiv$ $\displaystyle x^2+x+1$  

Below is an applet where the reader can multiply two vectors over $ \FF[2^6]$. This applet will take input numbers that are not mod2, but the product will be mod2.


next up previous contents
Next: Linear Codes Up: Spring 2004 Final Report Previous: Sentences as Numbers   Contents
Frederick Leitner 2004-05-12