Message Boards Message Boards

Basis of factors for large degree polynomials


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.

factors and basis

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.

basis in z2

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.

(Also at math.stackexchange )

16 days ago

I think you're going to run out of memory with i > 20, for example the number of terms with i = 15:

i = 15; Length[Factor[x^2^i + x + 1, Modulus -> 2]]

Not sure if it's helpful to you, but I noticed PolynomialRemainder will easily pass 1000:

Table[{i, PolynomialRemainder[x^2^i + x + 1, x^2 + x + 1, x, Modulus -> 2]}, {i, 1, 1000}]
POSTED BY: Stephan Foley
15 days ago

enter image description here - Congratulations! This post is now a Staff Pick as distinguished by a badge on your profile! Thank you, keep it coming!

POSTED BY: Moderation Team
3 days ago

Group Abstract Group Abstract