Basis of factors for large degree polynomials

Posted 1 year ago
2754 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[]]; 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], Row[Take[data, {7, 8}], Spacer], 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 ) Answer
2 Replies
Sort By:
Posted 1 year 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}] Answer
Posted 1 year ago - Congratulations! This post is now a Staff Pick as distinguished by a badge on your profile! Thank you, keep it coming! Answer