Construct Galois field extension from a given a Galois Field

Question

I am trying to construct $GF(4^2) = GF(q^m) = GF(p^{q^m}) = GF(2^{2^2})$ from $GF(4)$. Given is that $GF(4) = \{0, 1, \xi, \xi +1\}$ with $\xi^2+\xi+1=0$.

I know that I can construct this extension field by using an irreducible polynomial $p(x)$ of degree $m$ with coefficients in $GF(q)$ and constructing $GF(4)[x]|_{(p(x))}$. But I am struggling on how to construct $GF(4)|_{(p(x))}$ exactly in this case.

I have chosen $p(x) = x^2 + x\xi + \xi$ and $\alpha$ a root ($p(\alpha)=0$).
$\alpha$ should now be a primitive element that generates the multiplicative group $GF(4^2)$. I'm not sure on how to continue from here on.

EDIT
I found an answer for the same question here: How to construct $\mathbb{GF}(4^2)$ from $\mathbb{GF}(4)$?. Unfortunately, I don't understand the answer completely so perhaps I'm missing some knowledge that one of you could help me with. In the last part he says:

$GF(16)=\{a+b\alpha∣a,b∈GF(4)\}$

(He used $\beta$ where I used $\alpha$). I'm not sure how he just jumped to that conclusion.

(preparing for an exam.
I'm learning this stuff in a different language. Thus hopefully the translations for the mathematical names make sense!)

Answer 1

With the help of dan_fulea, I managed to find an answer:

----------
Question: Construct $GF(4^2)$ from $GF(4)$.
In other words: Find the extension field $GF(4^2)$ from $GF(4)$ (which is in my textbook referred to as the base field).

Given:

• $GF(4)=\{0, 1, \xi, \xi + 1\}$. Do not be scared by $\xi$, it is an element like any other in $GF(4)$.

Solution:
It is important to know the following fact: The extension field $GF(4^2)$ (but really any extension field) is isomorphic with the quotient ring of its base field and ideal. Translating this to our problem:

$GF(4)|p(x)$ (here: base_field|ideal) is isomorphic to $GF(4^2)$.
Thus we will attempt to construct this:

Step 1: Find $p(x)$.
This is fairly easy in our case. We first need to convert our base field notation, $GF(4)$, to $GF(p^k)$ in which $p$ is prime. It is easy to see that $GF(4)=GF(2^2)$. $p(x)$ should now be an irreducible polynomial over $GF(4)$ of degree $k$. Irreducible over $GF(4)$ meaning that no element in $GF(4)$ is a root for it.

After some brute force (checking all possible polynomials of degree 2 over $GF(4)$ until we find one without roots in $GF(4)$), we find:

$p(x) = x^2+x\xi+\xi$. (there are also other solutions for $p(x)$, but we'll be working with the one above).

Step 2: Introduce $\alpha$.
We now introduce a new element $\alpha \not\in GF(4)$ and say that it is a root for $p(x)$.
Thus: $p(\alpha) = \alpha^2+\alpha\xi+\xi = 0$.

Step 3: Find the remainders $r(x)$.
To construct $GF(4)|p(x)$, we divide every element in $GF(4)[x]$ by $p(x)$ and look at the remainders $r(x)$. Because $p(x)$ has degree 2, we know that all remainders $r(x)$ will have a degree $<2$ (you can convince yourself that this is true by trying it on some examples). Thus they will have the following form:
$r(x) = ax + b$ with $a,b \in GF(4)$

Step 4: Final.
$GF(4^2)$ now consists of every possible $r(\alpha)$. Because $GF(4^2)=GF(16)$, we know that the cardinality (amount of elements) of $GF(4^2)$ is 16. A quick check to indicate that the answer is probably correct is checking the cardinality by writing down all elements in $GF(4^2)$:

$GF(4^2) = \{0, 1, \alpha, \xi, \xi+1, \xi\alpha,(\xi+1)\alpha, \alpha+1, \alpha+\xi, \alpha+(\xi+1), \xi\alpha+1, \xi\alpha+\xi, \xi\alpha+(\xi+1), (\xi+1)\alpha+1, (\xi+1)\alpha + \xi, (\xi+1)\alpha + (\xi+1) \}$

And indeed, as expected there are 16 elements in $GF(4^2)$. We found these by simply making all possible combinations for $r(\alpha) = a\alpha + b$ with $a, b \in GF(4^2)$.

----------

Conclusion
In hindsight, this exercise was not particularly difficult. But, because of how abstract this is, (who would have thought, abstract algebra abstract?!) I often find it difficult to read through the material. Thus, this attempt to explain how this works with so many steps.

Answer 2

Here is a possible way to make the construction. We start with the field $L$ with $2^4=16$ elements, its multiplicative group of elements $\ne0$, $L^\times$ with the operation of multiplication inherited from $L$ is cyclic and has order $2^4-1=15=5\cdot 3$. Let us pick a generator of $L$. To have a clear example, i will use sage code:

sage: L.<g> = GF(2^4)
sage: g.multiplicative_order()
15
sage: g.minimal_polynomial()
x^4 + x + 1

I wanted only this $x^4+x+1$, (instead of factorizing $x^{15}-1$ with bare hands over $\Bbb F_2$,) please ignore now the code above. Let $g$ be a root in $L$ of this polynomial.

Then $a:=g^5=g(g^4)=g(g+1)=g^2+g$ has multiplicative order $3$, $(g^5)^3=1$, so $g^5$ is an element in the subfield $K$ with four elements of $L$, and $(K^\times,\cdot)$ is a subgroup with three elements of $(L^\times, \cdot)$.

It remains now to factorize $x^4+x+1$ over $\Bbb F_4=\Bbb F_2[a]$. We have together with $g$, letting the Frobenius isomorphism $x\to x^2$ act on $L$, the other roots $g^2, g^4, g^8$. So $$ (x-g)(x-g^2)(x-g^4)(x-g^8)=x^4+x+1\ . $$ Of course, we group factors in pairs, and after some trials and erros we see $$ (x-g)(x-g^4) = x^2\pm (g^4+g)x+g^5=x^2 + x + a\ . $$ This realizes $L$ as $K[x]$ modulo $(x^2+x+a)$.

For me this is the simplest way to construct $\Bbb F_{16}:\Bbb F_4$, in the above notations $L:K$, in an explicit manner.