# Factorization of polynomials in Galois Field 2

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

(1+x+x3)(1+x2+x3)(1+x)


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

What is the systematic rule for decomposing 1+x7?

• 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. – Jyrki Lahtonen May 12 at 21:17
• 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. – Jyrki Lahtonen May 12 at 21:19
• 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... – mahmood May 13 at 15:23
• 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, – 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)$$