I want to know what is the general rule for factorization of the generator polynomial which is based on Galois Field, GF2?

Fact is, a generator of degree m must divide 1+x^n where remainder is zero. for example 1+x^7 ca be written as


So either 1+x+x3 or 1+x2+x3 can be used.

What is the systematic rule for decomposing 1+x7?

  • $\begingroup$ Sounds like this is for using cyclic codes. In other words, the polynomial you want to factor will always be of the form $x^n+1$. Instead of the factors you can also use the idempotents of the cyclic code. Those are very straightforward to find. See a recent answer of mine. Actually Berlekamp's algorithm that Dietrich refers to begins by finding the idempotents modulo the polynomial to be factored. In general it is a bit more complicated, but for polynomials of this special form idempotents correspond to cyclotomic cosets. $\endgroup$ – Jyrki Lahtonen May 12 at 21:17
  • $\begingroup$ The step from idempotents to factors is a bit more complicated, but manageable. To get the minimal cyclic codes you want the so called orthogonal idempotents. I don't remember all the details, and it's too late an hour for me to think it through - may be tomorrow. $\endgroup$ – Jyrki Lahtonen May 12 at 21:19
  • $\begingroup$ Thanks. However, I have better feeling with the second answer in the link you posted. So, it seems that 1+xn is written as p.q.r where p=1+x. But I don't understand the rest. So, 1+x7 will be (1+x)(1+x2+x3+x4+x5+x6). I don't understand the rest then... $\endgroup$ – mahmood May 13 at 15:23
  • $\begingroup$ That's fine. Different answers bring up different points of view. I brought it up because in coding theory using the idempotents is one way of looking at. At least among math people - telcomm engineers less so. But really, idempotents are in a sense at the heart of Berlekamp. Every time you find a non-trivial polynomial $e(x)$ such that $e(x)^2\equiv e(x)\pmod {x^n+1}$ you can find a non-trivial factor of $x^m+1$ by calculating $\gcd(e(x), x^m+1)$. And that is trivial with the extended Euclid's algorithm, $\endgroup$ – Jyrki Lahtonen May 13 at 15:30

A systematic way is to apply the Berlekamp algorithm. It gives $$ x^7+1=(x^3 + x^2 + 1)(x^3 + x + 1)(x + 1), $$ as you said. Or $$ x^{11}+1=(x^{10} + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1)(x + 1) $$

| cite | improve this answer | |
  • $\begingroup$ I read that but I can not apply that for the example. Actually I don't know how to initialize that and how to find the GCDs. $\endgroup$ – mahmood May 12 at 14:46

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.