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

  • 3
    $\begingroup$ Have you looked at the Finite Fields package and could it satisfy your needs? $\endgroup$
    – F'x
    Apr 12, 2012 at 7:44
  • 3
    $\begingroup$ 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. $\endgroup$ Apr 12, 2012 at 16:46
  • $\begingroup$ 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)$. $\endgroup$
    – Sergey
    Apr 13, 2012 at 6:40

1 Answer 1


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},
   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
  • $\begingroup$ 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. $\endgroup$ Aug 24, 2012 at 14:52
  • 1
    $\begingroup$ 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]]]. $\endgroup$ Aug 24, 2012 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.