Find polynomial over Z2, that has the least degree, for which the field P=GF(64) is the minimum decomposition field. How much such polynomial are?

Question

Find polynomial over Z2, that has the least degree, for which the field P=GF(64) is the minimum decomposition field. How much such polynomials are?

Please, answer in detail! I think that these polynomials are all sixth irreducible polynomials, but I don't know how to validate this fact.

Answer 1

It's a general fact that $\mathbb{F}_p[x]/(q)$ is isomorphic to $\mathbb{F}_{p^n}$, where $q$ is an irreducible polynomial of degree $n$. Furthermore, $\mathbb{F}_p[x_1]$ is a splitting field for $q$ where we take $x_1$ to be a root for $q$ (we know that it contains $\mathbb{F}_{p^n}$; this says that they are the same). This is because $x, x^p, \ldots, x^{p^{n-1}}$ are all roots of $q$.

Thus we are looking for irreducible polynomials of degree $6$. We know they all must divide $x^{64}-x$, since every element of $\mathbb{F}_{64}$ satisfies that. Moreover, the roots of that are distinct (take the derivative) so we just need to factorize it and count the number with degree $6$.

The product of the irreducible polynomials with degree $d$ over all $d|n$ is $x^{2^n}-x$ (this can be deduced from the combining the fact that $\mathbb{F}_{p^m}\subset \mathbb{F}_{p^n}$ iff $m|n$ with the reasoning above).

Here, $p=2$ and $n=6$. There are obviously $2$ with degree $1$, which means there are $(2^2-2)/2 = 1$ of degree $2$, $(2^3-2)/3=2$ of degree $3$, and $(2^6-2-2-6)/6 = 9$ of degree $6$.

Finding one explicitly might be a bit annoying. It's not too hard to get that for $1, 2, 3$ they are $x, x+1, x^2+x+1, x^3+x+1, x^3+x^2+1$.

Now we want to remove some of the monomials from $x^6+x^5+x^4+x^3+x^2+x+1$ to make it irreducible, and we know we need to keep $x^6$. From degree 1 we need to remove an even number and we need to keep $1$. Ok so after some trials you will get an answer like $x^6+x^4+x^3+x+1$.

Answer 2

This late answer uses computer power to find explicitly the irreductible polynomials of degree six in $\Bbb F_2[X]$.

There exists up to isomorphy only one field with $2^6$ elements, $F=\Bbb F_{64}$, its elements are fixed by the corresponding Frobenius isomorphism, so $F$ contains the roots of $$x^{2^6}-x\ .$$ sage gives the following factorization for it:

sage: R.<x> = PolynomialRing( GF(2) )
sage: for f, multiplicity in ( x^(2^6) - x ).factor():
....:     print f
....:     
x
x + 1
x^2 + x + 1
x^3 + x + 1
x^3 + x^2 + 1
x^6 + x + 1
x^6 + x^3 + 1
x^6 + x^4 + x^2 + x + 1
x^6 + x^4 + x^3 + x + 1
x^6 + x^5 + 1
x^6 + x^5 + x^2 + x + 1
x^6 + x^5 + x^3 + x^2 + 1
x^6 + x^5 + x^4 + x + 1
x^6 + x^5 + x^4 + x^2 + 1

How many elements in $F$ are roots of a polynomial of degree exactly $6$? There are, by inclusion/exclusion $|F_{2^6}|-|F_{2^3}|-|F_{2^2}|+|F_{2^1}|=2^6-2^3-2^2+2=64-8-4+2=54$ such elements, so we expect $54/6=9$ (edited division...) irreducible polynomials of degree $6$ as factors above.