How are the addition and multiplication tables for $GF(4)$ constructed? I know this question has been asked many times and there is good information out there which has clarified a lot for me but I still do not understand how the addition and multiplication tables for $GF(4)$ is constructed?
I'm just starting to learn about fields in general, galois fields and the concept of "it can't be 0 or 1 so it must be x"
I've seen;
Galois Field GF(4);
Addition and Multiplication in $F_4$;
Explicit construction of a finite field with $8$ elements
but none explicity explain the construction and I'm too new to be told "its an extension of $GF(2)$"
Thank you in advance
 A: For any given $n$, there is at most one field with $n$ elements: only one, if $n$ is a power of a prime number ($2, 3, 2^2, 5, 7, 2^3, 3^2, 11, 13, \ldots$) and none otherwise ($6, 10, 12, 14\ldots$).  This field with $n$ elements is written as $\Bbb F_n$ or as $GF(n)$. 
Suppose we want to construct $\Bbb F_n$ where $n=p^k$.  When $k=1$, this is easy-peasy: take the $n$ elements to be the integers $0, 1, 2\ldots p-1$, and the addition and multiplication are done modulo $n$.
When $k>1$ it is more interesting.  One possible construction goes like this:


*

*The elements of $\Bbb F_{p^k}$ are the polynomials $$a_{k-1}x^{k-1} + a_{k-2}x^{k-2} + \ldots + a_1x+a_0$$ where the coefficients $a_i$ are elements of $\Bbb F_p$.  That is, the  coefficients are just integers in $\{0, 1, \ldots p-1\}$, but with the understanding that the addition and multiplication will be done modulo $p$.  Note that there are $p^k$ of these polynomials in total.

*Addition of polynomials is done exactly as usual: combine like terms, but remember that the the coefficients are added modulo $p$ because they are elements of $\Bbb F_p$.

*Multiplication is more interesting:
a. Pick an irreducible polynomial $P$ of degree $k$.  “Irreducible” means that it does not factor into a product of smaller polynomials.  How to actually locate an irreducible polynomial is an interesting question; here we will mostly ignore it.
b. To multiply two elements, multiply them normally, remembering that the coefficients are in $\Bbb F_p$.  Divide the product by $P$ and keep the remainder.  Since $P$ has degree $k$, the remainder must have degree at most $k-1$, and this is your answer.

Now we will see an example: we will construct $\Bbb F_{2^2}$.  Here $k=2$ and $p=2$. The elements will be polynomials of degree at most 1, with coefficients in $\Bbb F_2$.  There are four elements: $0x+0, 0x+1, 1x+0, $ and $1x+1$. As usual we will write these as $0, 1, x, x+1$.  This will not be misleading.
Addition is straightforward: combine like terms, remembering that $1+1=0$ because the coefficients are in $\Bbb F_2$:
$$\begin{array}{c|cccc}
+ & 0 & 1 & x & x+1 \\ \hline 
0 & 0 & 1 & x & x+1 \\
1 & 1 & 0 & x+1 & x \\
x & x & x+1 & 0 & 1 \\
x+1 & x+1 & x & 1 & 0
\end{array}
$$
The multiplication as always is more interesting.  We need to find an irreducible polynomial $P$.  It so happens that $P=x^2+x+1$ is the only one that works.  (If you didn't know this, you could find out easily: a reducible polynomial of degree 2 factors into two linear factors.  So the reducible polynomials are $x^2, x·(x+1) = x^2+x$, and $(x+1)^2 = x^2+2x+1 = x^2+1$.  That leaves only $x^2+x+1$.) 
To multiply two polynomials, we multiply them normally, then divide by $x^2+x+1$ and keep the remainder.  For example, what is $(x+1)(x+1)$?  It's $x^2+2x+1 = x^2 + 1$. There is a theorem from elementary algebra (the “division theorem”) that we can find a unique quotient $Q$ and remainder $R$, with the degree of $R$ less than 2, such that $PQ+R = x^2+1$.  In this case, $Q=1, R=x$ works.  (You should check this.)    Since $R=x$ this is our answer: $(x+1)(x+1) = x$.
Let's try $x·x = x^2$.  We want $PQ+R = x^2$, and it happens that $Q=1, R=x+1$ works.  So $x·x = x+1$. 
I strongly recommend that you calculate the multiplication table yourself.  But here it is if you want to check:
$$\begin{array}{c|cccc}
· & 0 & 1 & x & x+1 \\ \hline 
0 & 0 & 0 & 0 & 0 \\
1 & 0 & 1 & x & x+1 \\
x & 0 & x & x+1 & 1  \\
x+1 & 0 & x+1 & 1 & x
\end{array}
$$
To calculate the unique field $\Bbb F_{2^3}$ of order 8, you let the elements be the 8 second-degree polynomials $0, 1, x, \ldots, x^2+x, x^2+x+1$ and instead of reducing by $x^2+x+1$, you reduce by $x^3+x+1$.  (Not by $x^3+x^2+x+1$, because that factors as $(x^2+1)(x+1)$.)   To calculate the unique field $\Bbb F_{3^2}$ of order 27, you start with the 27 third-degree polynomials with coefficients in $\{0,1,2\}$, and you reduce by $x^3+2x+1$ (I think).

The special notation $\Bbb F_p[x]$ means the ring of all polynomials with coefficients from $\Bbb F_p$.  $\langle P \rangle$ means the ring of all multiples of polynomial $P$. (A ring is a set with an addition, subtraction, and multiplication defined.)
When we write $\Bbb F_p[x] / \langle P\rangle$ we are constructing a thing called a “quotient” structure.  This is a generalization of the process that turns the ordinary integers $\Bbb Z$ into the modular-arithmetic integers we have been calling $\Bbb F_p$.  To construct $\Bbb F_p$, we start with $\Bbb Z$ and then agree that two elements of $\Bbb Z$ will be considered equivalent if they differ by a multiple of $p$.
To get $\Bbb F_p[x] /  \langle P \rangle$ we start with $\Bbb F_p[x]$, and then agree that elements of $\Bbb F_p[x]$ will be considered equivalent if they differ by a multiple of $P$.  The division theorem guarantees that of all the equivalent polynomials in a class, exactly one of them will have degree less than that of $P$, and that is the one we choose as a representative of its class and write into the multiplication table. This is what we are doing when we “divide by $P$ and keep the remainder”.

A particularly important example of this construction is $\Bbb R[x] / \langle x^2 + 1\rangle$.  That is, we take the set of polynomials with real coefficients, but we consider two polynomials  equivalent if they differ by a multiple of $x^2 + 1$.  By the division theorem, each  polynomial is then equivalent to some first-degree polynomial $ax+b$.  
Let's multiply $$(ax+b)(cx+d).$$ As usual we obtain $$acx^2 + (ad+bc)x + bd.$$  From this we can subtract $ac(x^2 + 1)$ to obtain the equivalent first-degree polynomial $$(ad+bc) x + (bd-ac).$$
Now recall that in the complex numbers, $(b+ai)(d + ci) = (bd-ac) + (ad+bc)i$.  We have just constructed the complex numbers,with the polynomial $x$ playing the role of $i$.
A: Well, take an irreducible polynomial of degree 2 over $GF(2)$. There is exactly one namely $f(x)=x^2+x+1$.
Then the quotient ring $GF(2)[x]/\langle f(x)\rangle$ is a field, $GF(4)$, with 4 elements.
To construct the field, note that $f(x)$ has a zero in $GF(4)$ namely residue class $x+\langle f(x)\rangle$. Call it $\alpha$. Then $f(\alpha)=\alpha^2+\alpha+1=0$, i.e., $\alpha^2=\alpha+1$.
Thus the elements of $GF(4)$ are $0,1,\alpha,\alpha^2=\alpha+1$. From here its simple to construct the addition and multiplication tables.
