# 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[]]; 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 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}] Answer
Posted 3 years ago - Congratulations! This post is now a Staff Pick as distinguished by a badge on your profile! Thank you, keep it coming! Answer