Normal basis of $GF(2^4)$ over $GF(2^2)$

Question

I'm reading this paper: Scrutinizing the Tower Field Implementation of the $F(2^8)$ Inverter – with Applications to AES, Camellia, and SM4. It mentioned a sequence of field extensions $F_2 \subseteq F_{2^2} \subseteq F_{2^4} \subseteq F_{2^8}$. Let $r(y) \in F_{2^4}[y], s(z) \in F_{2^2}[z], t(w) \in F_2[w]$ be irreducible polynomials over their respective fields, and let $Y \in F_{2^8}, Z \in F_{2^4}, W \in F_{2^2}$ be roots of $r(y),s(z),t(w)$ over the corresponding fields respectively. Then it obtain a set of normal basis: $[Y^{16},Y]$ is a basis of $F_{2^8}$ over $F_{2^4}$, $[Z^4,Z]$ is a basis of $F_{2^4}$ over $F_{2^2}$, $[W^2,W]$ is a basis of $F_{2^2}$ over $F_{2}$.
But I really don't understand how to get $[Y^{16},Y], [Z^4,Z], [W^2,W]$. HELP!

Answer 1

• $F_{p^{2n}} = F_{p^n}[x]/(x^2+ax+b)$ for any $x^2+ax+b\in F_{p^n}[x]$ irreducible.

• $F_{p^n}$ is the splitting field of $x^{p^n}-x\in F_p[x]$.

• The $F_{p^n}$-conjugate of $x$ is $x^{p^n}$ and $x,x^{p^n}$ is a normal basis of $F_{p^{2n}}/F_{p^n}$ iff $x,x^{p^n}$ are $F_{p^n}$-linearly independent iff $x^{p^n-1}$ is not in $F_{p^n}$.

If $x^{p^n-1}\in F_{p^n}$,

Then $(x^{p^n-1})^{p^n-1}=1$.

On the other hand $x\in F_{p^{2n}}$ implies that $x^{p^{2n}-1}=1$.

Together this would imply that $x^{\gcd(p^{2n}-1,(p^n-1)^2)}=1$.

Now we assume that $p=2$, then $\gcd(2^{2n}-1,(2^n-1)^2)=2^n-1$ so $x^{2^n-1}=1$ ie. $x\in F_{2^n}$ which is a contradiction.

Whence $x,x^{2^n}$ is always a normal basis.