# Find roots of polynomial in field extension $GF(2^n)$?

How can I find roots of polynomial in extension field $GF(2^n)$?

• Have you looked at the Finite Fields package and could it satisfy your needs? – F'x Apr 12 '12 at 7:44
• What is your representation of this extension of Z_2? Are you starting with a polynomial irreducible over Z_2 and of degree n? Or something that factors, with highest degree factor being n? Or something else altogether? How will you want the roots represented? I do not know whether I can suggest a direction to take, but these issues need to be sorted out before one can go further. – Daniel Lichtblau Apr 12 '12 at 16:46
• Thank You for help! I have plynomial, for example $x^8+x^7+x^5+x^3+1$. It is irreducible over $GF(2)$, but has its roots in some extension $GF(2^n)$. I need to find these roots as elements of $GF(2^n)$. – Sergey Apr 13 '12 at 6:40

Well, for your example $p(x)=x^8 + x^7 + x^5 + x^3 +1$, the associated extension $GF(2^n)\cong \frac{GF(2)[x]}{\langle p(x) \rangle}$ is a vector space over $GF(2)$ of dimension $8$. The elements of this field can be written as polynomials $a_0+a_1x+\ldots +a_7x^8$ for $a_i\in GF(2)$. By quotienting we've insisted that $p(x)=0$, so the multiplication between these elements defined by first multiplying the polynomials as usual (taking addition modulo 2), then reducing by $p(x)$. For example, $(x^2+x^4+x^6+x^7)x=1$.

A quick and dirty Mathematica mockup to implement this is

modpoly[p_] := Module[{J},
J = Mod[#, 2] & /@ CoefficientList[p, x];
Total[Table[J[[i]] x^(i - 1), {i, 1, Length[J]}]]
]
multiply[p_, q_] := Module[{K},
modpoly[
PolynomialMod[modpoly[Expand[p q]], x^8 + x^7 + x^5 + x^3 + 1]]
]


which yields, for example,

multiply[x^2 + x^5 + x^6, x + x^6 + x^7]

> 1 + x + x^2 + x^5

• Thx for responding (I never saw that my question had been answered). One thing to add is that by definition the extension field element represented by 'x' is itself a root of the given polynomial. There will be others, of course. – Daniel Lichtblau Aug 24 '12 at 14:52
• modpoly[] can be written very compactly using a dot product: modpoly[p_] := Mod[CoefficientList[p, x], 2].x^Range[0, Exponent[p, x]]. Alternatively, you can use Horner's method: modpoly[p_] := Expand[Fold[(#1 x + #2) &, 0, Reverse@Mod[CoefficientList[p, x], 2]]]. – J. M. will be back soon Aug 24 '12 at 15:53