I wonder how to construct the irreducible polynomial of a composite field $GF((2^m)^n)$, where $q=mn$.
According to the example, the primitive polynomial of $GF(2^4)$ is $x^4 + x +1$. However, why the primitive polynomial of $GF((2^4)^2)$ is $x^2 + x + \{0 0 0 1\}$. Where the $\{ 0 0 0 1\}$ comes from?
Edit: Here presumably $\{0001\}$ lists the coordinates of an element of $GF(2^4)$ with respect to the basis consisting of powers $1,a,a^2,a^3$ where $a$ is a zero of $x^4+x+1$ (and hence a primitive element). In other words $\{0001\}=a^3$, JL
Assuming that $\{0001\}$ truly stands for the element $\alpha^3$, where $\alpha$ is a root of $x^4+x+1$, it follows that a zero $\beta$ of $x^2+x+\alpha^3$ is not a primitive element of $GF(256)$.
This is seen as follows. Recall that $\alpha$ is of order fifteen, so $\gamma:=\alpha^3$ is a fifth root of unity, and its minimal polynomial is $x^4+x^3+x^2+x+1$. We have the relation $$ \beta^2+\beta=\gamma. $$ Squaring this three times and using $\gamma^5$ gives as consequences $$ \begin{aligned} \beta^4+\beta^2&=\gamma^2,\\ \beta^8+\beta^4&=\gamma^4,\\ \beta^{16}+\beta^8&=\gamma^8=\gamma^3. \end{aligned} $$ Summing all these four equation gives us after cancellations on the left hand side $$ \beta^{16}+\beta=\gamma+\gamma^2+\gamma^3+\gamma^4=1. $$ So we can conclude that $\beta^{16}=\beta+1$ Multiplying this by $\beta$ gives $$ \beta^{17}=\beta^2+\beta=\gamma. $$ As $\gamma$ has order five, it follows that $\beta^{85}=1$, so $\beta$ is not a primitive element of $GF(256)$ (that would have to be of order $255$).
However, the polynomial $x^2+x+\gamma$ is irreducible over $GF(16)$. This is because $tr(\gamma)=1$, and this is exactly the well known irreducibility criterion. Therefore the field extension $GF(2)(\beta)=GF(256)$. If the author uses primitive in this sense (as opposed to in the standard finite field sense of primitive=generator of the multiplicative group), then the claim holds. But then the exercise would simply call you to prove that the quadratic $x^2+x+\gamma$ is irreducible, so this doesn't really hold water.
Unless I made a mistake, the minimal polynomial of $\beta$ over the prime field is $$ m(x)=x^8+x^6+x^5+x^4+x^3+x+1. $$