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.


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$.

  • $\begingroup$ Thank you very much for your explanations! And is it easier to sort out all irreducible polynomials of degrees 1, 2, 3, 4, 5, 6? I mean that is it right only to show that irreducible polynomials of degree 1 splits over GF(4), 2 --- splits over GF(8), ..., 5 --- splits over GF(32). And then say that if a 6th degree polynomial isn't irreducible, it contains irreducible polynomials of degrees 1, 2, 3, 4 or 5. So, all 6th degree irreducible polynomials split over GF(64). And then show their splits. $\endgroup$ – alexhak May 10 '18 at 16:00

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 + 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.

  • $\begingroup$ Thanks very much! It solves my problem $\endgroup$ – alexhak May 10 '18 at 20:22
  • $\begingroup$ WA also helps. $\endgroup$ – lhf May 10 '18 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.