# Construction of addition and multiplication table for GF(4)

I am dealing with finite fields and somehow got stuck. The construction of a prime field $GF(p), p \in \mathbb{P}$ is pretty easy because every operation is modulo p. In other words $GF(p)$ contains all integers ranging from 0 to $p-1$.

However, non prime fields are a bit trickier. Given the power $q = p^n$ with $p \in \mathbb{P}$ and $n \in \mathbb{N}$, one has to find an irreducable polynom g(x) of degree n. Then the construction of $GF(p^n)$ is the following:

$GF(p^n) = \frac{GF(p)[x]}{g}$

Theoretically I get along with this definition. Unfortunately I fail to construct addition and multiplication tables for any GF(q). Though I can easily find the wanted table on the internet, I have not found an explication yet that really made me understand.

I would like to know how to create the addition and multiplication table for $GF(2^2)$ with the above knowledge. $GF(2^2)$ contains four elements. Let's call them $\{0,1, \alpha, \beta \}$. $g$ must be $x^2 + x + 1$ as there no other irreducable polynom of degree 2. So far I am able to construct the addition table partly (question marks indicating despair...):

## $\beta$ | $\beta$ ? ? ? |

I don't understand how to calculate for example $1+\alpha$. The result is $\beta$, but I don't know why. Concerning the above short explanation, I have to divide $1+\alpha$ by $g$. But how can I do this?

• You're forgetting a very important part of the construction: $$\alpha = X \\ \beta = X+1$$ May 25, 2015 at 21:27
• Our site search function leaves a few things to be desired, but if you use the string GF(4), the first hit it offers is this question. Does that help? Once you get the hang of using the polynomial $g$ things become a lot easier. I prepared this Q&A pair partly with referrals like this in mind. May 26, 2015 at 5:08
• What is the relationship between those polynomials and $\alpha$, $\beta$? How do I create them?
– null
May 26, 2015 at 14:06

This case is fairly easy because all the calculations are modulo 2 and the field has only 4 elements. Let $\alpha$ be a root of $g$, i.e, $\alpha^2 + \alpha + 1 = 0$. This immediately implies that $1+\alpha = -\alpha^2 = \alpha^2$, which you are calling $\beta$. I would suggest to try a polynomial of higher degree so that the field has more elements.
• Why are all calculations modulo 2? $p$ in $GF(p) = GF(2^2)$ is not prime and therefore you should divide by the irreducible polynom (see above).
• I meant operations on the prime field, which in this case is $\{0,1\}$. So basically you have to deal only with $\alpha$ and $\beta = 1+\alpha$. Then $\alpha + \beta = 1+2\alpha = 1$. May 26, 2015 at 14:12