Irreducible Polynomial $g = X^4 + X + 1$ in $\mathbb{F}_2$

Question

I have the Irreducible Polynomial $g = X^4 + X + 1$ over $\mathbb{F}_2$, and $E$ the extension of $\mathbb{F}_2 = \{0,1\}$ with root $\alpha$ of $g$.

My previous problems have asked me to find the number of elements in $E$ and see if they may all be represented in the form $\alpha^n$ with $n \in \mathbb N$ (I believe the answer to these are 16 and no respectively).

I am struggling however to find all the roots of $g$ in $E$ expressed in the form $\nu + \mu\alpha + \lambda \alpha^2 + \gamma \alpha^3$ as my final problem has posed.

Any help would be kindly appreciated.

Answer 1

1. Recall that the multiplicative group of $E$ is cyclic of order 15 ( because it omits 0).
2. It's a convenient fact that if $r$ is a root of a polynomial over $\Bbb F_2$, then $r^2$ is also. (You prove this, or at least check that it's true for the cases you know about.)

So if you have one root of a polynomial over $\Bbb F_2$ (which you do, $\alpha$) it's usually easy to find the others.

Does this help? If not, can you say more about where you got stuck?

Answer 2

I suppose that $E=\mathbb{Z}_2[x]/I$, $I$ being the ideal $<x^4+x+1>$. By Kronecker's theorem the first root is of course $a=x+I$. Keep in mind that $char(E)=2$. Therefore, since $a^4+a+1=0$, one has $(a^4+a+1)^2=0$, but because of the characteristic, this is the same as $a^8+a^2+1=0$, therefore $a^2=x^2+I$ is another root. Keep going: $a^4, a^8$ are the rest of the roots. To express them in the form $a_0+a_1x+a_2x^2+a_3x^3$ with $a_i\in\mathbb{Z}_2$, just use the Euclidean division algorithm to divide $x^4, x^8$ with $x^4+x+1$. The remainders are the desired expressions.