Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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

share|improve this question
3  
Have you looked at the Finite Fields package and could it satisfy your needs? –  F'x Apr 12 '12 at 7:44
3  
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
add comment

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},
  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
share|improve this answer
    
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
1  
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. Aug 24 '12 at 15:53
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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