How can I find roots of polynomial in extension field $GF(2^n)$?
3
-
3$\begingroup$ Have you looked at the Finite Fields package and could it satisfy your needs? $\endgroup$– F'xApr 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$– Daniel LichtblauApr 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$– SergeyApr 13, 2012 at 6:40
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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
-
$\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