Find the splitting field of this polynomial over GF(2)

Question

The polynomial is $x^4 + x + 1$ and I want to find its splitting field over GF(2).

$x^4 + x + 1$ does not have any linear factors in GF(2). So if I let $\omega$ to be a factor of the polynomial such that it lies it the algebraic closure of GF(2), we have $\omega^4 + \omega + 1=0$. But I'm not sure how to get the other roots from here...

Also, what is the degree of the splitting field over GF(2)?

Answer 1

I would use $\mathbb{F}_2$ as notation for the Galois Field of order $2$.

We know that adjoining $\omega$ to $\mathbb{F}_2$ generates a field of order $16$, call it $\mathbb{F}_{16}$, as $\mathbb{F}_{16} = \mathbb{F}(\omega) \cong \mathbb{F}_2[x]/\langle x^4 + x + 1 \rangle $. Now as the field is finite we have that the multiplicative group is cyclic of order $16-1=15$. Using the fact that $\omega, \omega^3, \omega^5 \not =1$ we conclude that $\mathbb{F}_{16}^{\times} = \langle \omega \rangle$

Now if the polynomial has another root in $\mathbb{F}_{16}$ then it must be a generator of $\mathbb{F}_{16}^{\times}$, as any generators are mapped to generators by automorphisms. Indeed a little bit of calculation gives you that $\omega, \omega^2, \omega^4, \omega^8$ are all of the roots, so $\mathbb{F}_{16}$ is the spliting field of $\omega$ over $\mathbb{F}_2$.

In fact if you are familiar with finte fields, you don't need all these calculations. Indeed for any finite field extension $L/F$ of characteristic $p$ we have that the Frobenius map $\sigma:x \to x^p$ is an automorphism of $L$ fixing $F$ pointwise. Moreover its order is exactly $[L:F]$. In particular applying it repeatedly to $\alpha \in F(\alpha)$, where $\alpha$ is a root of separable irreducible polynomial $f$ over $F$, will give us exactly $[F(\alpha):F] = \deg f$ roots, which must be all the roots of $f$. Hence $F(\alpha)$ is the splitting field of $f$ over $F$ and all the roots are $\{\alpha^{p^k} | 0 \le k \le \deg f - 1\}$.

Anyway if you are interested you can read more in the following article.

Answer 2

A beginning of a solution...

Either $p(x) = x^4+x+1$ is irreducible on $GF(2) = \mathbb F_2$, either it is the product of degree $2$ irreducible polynomials. The only degree $2$ irreducible polynomial is $q(x) = x^2 + x +1$. If $p$ was reducible, we would have: $$p(x)=x^2+x+1=(x^2+x+1)^2=x^4+x^2+1$$ which isn't the case. Hence $p$ is irreducible over $\mathbb F_2$, the degree of the splitting field $K$ of $p$ over $\mathbb F_2$ is at least equal to $4$ and $K$ contains $GF(2^4) = \mathbb F_{2^4}$.

We now have to analyze if $p$ splits in $\mathbb F_{2^4}$. Let's denote $\omega \in \mathbb F_{2^4}$ such that $$p(x)=x^4+x+1 = (x - \omega)(x^3+\omega x^2 + \omega^2 x + \omega^3+1).$$

We need to understand if $r(x)=x^3+\omega x^2 + \omega^2 x + \omega^3+1$ is reducible on $\mathbb F_{2^4}$. That is equivalent to know if $r$ has a root in $\mathbb F_{2^4}$... And for answering that question, I don't have a better solution than testing all the elements of $\mathbb F_{2^4}$!