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 '12 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$ – Daniel Lichtblau Apr 12 '12 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 '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},
   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$ – Daniel Lichtblau Aug 24 '12 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$ – J. M. will be back soon Aug 24 '12 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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