How to factorize polynomial in GF(2)?

Question

I want to know how to factorize polynomials in $\ GF(2) $ without a calculator in a product of irreducible factors. For example, in my exercises, I must factorize $\ p(x) = (x^7 - 1)$

The response is $\ (x − 1)(x^3 + x^2 + 1)(x^3 + x + 1)$

I just not understand the methodology to do it just by hand.

thanks a lot.

Answer 1

The methodology of factoring of a polynomial $f(x),$ $\deg f=n$:

1) find all irreducible polynomials up to degree $\dfrac{n}{2}.$

2) divide $f(x)$ on every of the irreducible polynomials.

Answer 2

for that particular example you have $7=2^3-1$ where $2$ is the characteristic. this means that $x^7-1$ is the product of all the irreducible polynomials whose degree divides $3$.

there is only one such polynomial of degree $1$, namely $x \pm 1$ (they are the same since $1 \equiv_2 -1$). for degree $3$ there are the two polynomials $x^3 \pm x^2 \pm 1$ and $x^3 \pm x \pm 1$

(NB any polynomial over $F_2$ with an even number of non-zero terms has the linear factor $x \pm 1$)