# Basis of factors for large degree polynomials

Posted 3 years ago
5286 Views
|
2 Replies
|
7 Total Likes
|
 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.(Also at math.stackexchange )
2 Replies
Sort By:
Posted 3 years 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]] 1096 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}]