How to find the roots of $ x^4 + x + 1$ in the extension of $\Bbb F_2$? Let $h$ the irreducible polynomial over $\Bbb F_2 = \{0, 1\}$
$$h  =  x^4 +x +1$$
Let $E=\Bbb F_2(\alpha)$, i.e. the field $\Bbb F_2$ extended with $\alpha$, where $\alpha$ is a root of $h$.


*

*How do we determine the numbers of elements in the extension $E$?

*Can every non-zero element in the extension be expressed in the form $(\alpha)^n$ for some $n\in\Bbb N$ ?

*How do we find all the roots of $h$ over the extension $E$?
 A: Since $h$ is irreducible, the degree of the extension $[E:\mathbb{F}_2]=4$.  Since $|\mathbb{F}_2|=2$, then $|E|=2^4=16$.  More precisely, $\{1,\alpha,\alpha^2,\alpha^3\}$ form a basis for $E$ over $\mathbb{F}_2$ and every element of $E$ can be written as $a_0+a_1\alpha+a_2\alpha^2+a_3\alpha^3$ where each $a_i$ is either $0$ or $1$ (an element of $\mathbb{F}_2$).
To see if every nonzero element in the extension can be written as a power of $\alpha$, we need to determine the order of $\alpha$ in $E^\ast$ (the group of multiplicative elements).  By the primitive element theorem, we know that as a group $E^\ast$ is cyclic, so $E^\ast=\mathbb{Z}/15$.  Therefore, we can compute the order of $\alpha$.  We know that $\{\alpha,\alpha^2,\alpha^3\}$ are independent; moreover, since $\alpha$ is a root of $h$, we know that $\alpha^4+\alpha+1=0$ or that $\alpha^4=\alpha+1$ which is not $1$ (note that there are no negatives in a field of characteristic 2).  Similarly, $\alpha^5=\alpha^2+\alpha$, which is not $1$ by the independence of the first few powers of $\alpha$.  Therefore, since $\mathbb{Z}/15$ has elements of order $1$, $3$, $5$, and $15$, and $\alpha$ is not order $1$, $3$, or $5$, it must be order $15$.  Therefore, every nonzero element of $E$ is a power of $\alpha$.  (Alternatively, you can just compute the powers of $\alpha$ and see that you get $15$ different values for $\alpha^n$, using that $\{1,\alpha,\alpha^2,\alpha^3\}$ are independent and $\alpha^4=1+\alpha$.)
To find the other roots of $h$, we can use Frobenius.  Namely, consider $h^2$, $x^8+2x^5+2x^4+x^2+2x+1=x^8+x^2+1=(x^2)^4+x^2+1$.  Therefore, if $\alpha$ is a root of $h$, then $\alpha^4+\alpha+1=0$ and squaring both sides gives $\alpha^8+\alpha^2+1=0$, but this is the same as $\alpha^2$ being a root of $h$.  In more generality, if $\beta$ is a root of $h$, then so is $\beta^2$.  Therefore, $\alpha$, $\alpha^2$, $\alpha^4=\alpha+1$, and $\alpha^8=\alpha^2+1$ are the roots of $h$.  (Note that $\alpha^{16}=(\alpha^2+1)^2=\alpha^4+1=(\alpha+1)+1=\alpha$ so that the next square does not give a new root.)
