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

Question

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

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},
  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