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

$$2*2\equiv4 1*3\equiv3 4*0\equiv0$$

$$2*3\equiv6\equiv1 3*5\equiv15\equiv0 3*5\equiv3*0\equiv0$$

$$7+9\equiv2+4\equiv6\equiv1$$

$$\underline{notice} \underbrace{ x + 0 \equiv 0}_{\textrm{additive identity}} \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.

$$\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$

$$\mathbb{R}[x] = \{a+bx\vert a,b\epsilon\mathbb{R}\}$$

$$(a+bx)*(a'b'x) = aa'+(a'b+b'a)x+bb'x^2$$

$$= aa'+(a'b+b'a)x+(-1)bb'$$

$$= (aa'-bb')+(a'b+b'a)$$

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

$$x^2+1 =$$ 0

$$x^2 = -1$$

$$x = \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}''

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

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

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

$$f(x) = 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] \}$ =

$$\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
$\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

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

$$x^2 \equiv -x-1$$

$$\equiv 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]$:

$$\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

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

$$\equiv x^3+2x^2+x$$

$$\equiv x^3+x$$

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

$$\equiv 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.