Basis of factors for large degree polynomials

Question

In $\mathbb{Z}_2$, the polynomial $x^{2^6}+x+1$ or $x^{64}+x+1$ factors into $x^4+x+1$, $x^{12}+x^9+x^5+x^2+1$, $x^{12}+x^9+x^5+x^4+x^2+x+1$, $x^{12}+x^9+x^8+x^5+1$, $x^{12}+x^9+x^8+x^5+x^4+x+1$, $x^{12}+x^9+x^8+x^6+x^3+x^2+1$. Below, under $1+x+x^{64}$, you can see the degree 12 factors arranged as columns, followed by the basis (a gray bar separates factors and basis). The same is shown for $n$ from 5 to 13.

In $\mathbb{Z}_2$, $x^{2^n}+x+1$ has many factors of degree $2 n$ and the number of basis elements always seems to be $n-2$. Here are pictures of the basis for $n$ from 7 to 18.

Here's Mathematica code for the first image.

data = Table[Module[{ polynomials, len, polyandbasis},
  polynomials = Last[Sort[SplitBy[SortBy[CoefficientList[#, x] & /@ (First /@ 
  FactorList[x^(2^power) + x + 1, Modulus -> 2]), {Length[#], Reverse[#]} &], Length[#] &]]];
  len = Length[polynomials[[1]]];
  polyandbasis = Flatten /@ Transpose[{ 3 Transpose[polynomials], Table[{0, 1, 0}, {len}], 
  3 Transpose[Select[RowReduce[polynomials, Modulus -> 2], Total[#] > 0 &]]}];
  Column[{Text[x^(2^power) + x + 1], ArrayPlot[polyandbasis, PixelConstrained -> True, 
  ImageSize -> {800, 2 len + 4}, Frame -> False]}, Alignment -> Center]], {power, 5, 13}];
Column[{Row[Take[data, 6], Spacer[30]], Row[Take[data, {7, 8}], Spacer[60]], Row[Take[data, {9}]]}] 

First question: Does the $\mathbb{Z}_2$ polynomial $x^{2^n}+x+1$ have a particular name? It has a lot of nice properties.

I'd like to make pictures of higher order basis elements. Unfortunately, Mathematica doesn't want to Factor $x^{1048576}+x+1$, claiming it's out of bounds. Also, PolynomialGCD doesn't like high exponents. I've looked at the Cantor–Zassenhaus algorithm and other factorization methods over finite fields, but didn't readily understand them.

Is there some clever way to get the basis of the $\mathbb{Z}_2$ factors of $x^{2^n}+x+1$ for $n$ from 19 to 120 in Mathematica? Is there some nice way of quickly getting some of the degree $2n$ factors.

Answer 1

Not a full answer, just the fruits of my first session thinking about this question. The main reason for posting this is that I can prove the following:

Result 1. The described basis has size at most $n-2$.

My older answer allows us to give the following description for the degree $2n$ factors of $x^{2^n}+x+1$.

• Assume that $p(x)=x^n+x^{n-1}+a_{n-2}x^{n-2}+\cdots+a_2x^2+a_1x+1$ is irreducible (take notice of the terms of degrees $0,n-1,n$). Then the polynomial $p(x^2+x)$ is an irreducible degree $2n$ factor of $x^{2^n}+x+1$. This follows from the description in the linked answer as the (negative of) coefficient of $x^{n-1}$ is the trace of the zeros of $p(x)$.
• All the irreducible degree $2n$ factors of $x^{2^n}+x+1$ are gotten following the recipe of the previous bullet for some such irreducible polynomial $p(x)$. See the linked answer again.
• Let $p(x)$ be one of the polynomials from the first bullet. Because $x+1$ is not a factor of $p(x)$, there is an odd number of non-zero terms in $p(x)$. Consequently the difference $$p(x)-(1+x^{n-1}+x^n)$$ has an even number of terms, all with degrees in the range $[1,n-2]$. Therefore $p(x)$ is in the linear span of $x+x^2,x+x^3,\ldots,x+x^{n-2},1+x^{n-1}+x^n$.

Proof. (of Result 1.) Consider the linear mapping $R:\Bbb{F}_2[x]\to\Bbb{F}_2[x]$ given by the formula $$ R(f(x))=f(x^2+x). $$ The third bullet above implies that the irreducible degree $2n$ factors of $x^{2^n}+x+1$ are all in the linear span of $$ R(x+x^2),R(x+x^3),\ldots,R(x+x^{n-2}),R(1+x^{n-1}+x^n). $$

There are $n-2$ polynomials in this list so the subspace of $\Bbb{F}_2[x]$ spanned by the said factors has dimension at most $n-2$. QED.

I also record the following trivial fact for future use because it may play a role.

Because $\deg R(f(x))=2\deg f(x)$ for all polynomials $f(x)$, we see that the linear mapping $R$ is injective.