List all polynomials in $\mathbb F_2[x]$ that are minimal polynomials of elements from $\mathbb F_{16}$.
Since minimal polynomials are irreducible, this problem just asks to list irreducible polynomials of certain degrees over $\mathbb F_2$. But I have a hard time realizing what degrees I should consider. Does it have to do with the fact about the orders of subfields of finite fields? I'm not sure how to apply it.
Best Answer
The elements of $\mathbb F_{2^4}$ are the roots of $x^{2^4}-x$. By the general theory, the irreducible factors of $x^{p^r}-x$ over $\mathbb F_p$ are the irreducible polynomials in $\mathbb F_p[x]$ whose degrees divide $r$. Thus we need to list all irreducible polynomials over $\mathbb F_2$ of degrees $1,2,4$.
Degree $1$: $x,x+1$.
Degree $2$: $x^2+x+1$ (the other three polynomials have roots in the field).
Degree $4$: write out all polynomials of degree $4$ (there are $16 $ of them) and cross out those having roots. The remaining polynomials are $$x^4+x^3+x^2+x+1,x^4+x^2+1,x^4+x+1,x^4+x^3+1.$$ We need to delete from this list the polynomials that have an irreducible factor of degree $2$. Since the only irreducible polynomial of degree $2$ is $x^2+x+1$ and $(x^2+x+1)^2=x^4+x^2+1$, the three polynomials $x^4+x^3+x^2+x+1,x^4+x+1,x^4+x^3+1$ form a complete list of degree $4$ irreducible polynomials.