# Factorising polynomials in to their irreducible factors over GF(2)

A skill I'm trying to learn/understand is how to do this manually. I've noticed as a predecessor to a lot of my discrete maths example questions we are asked to obtain the irreducible factorisation of things like $$x^{15}-1, x^{18}-1, x^{20}-1 \in\mathbb{F_2[x]}.$$

What approach should one take generally when trying to do something like this? I've tried practising with smaller ones which are easier to do but I can't really see a general technique.

For $x^{18}-1=(x^9-1)^2=(x^3-1)^2(x^6+x^3+1)^2=(x-1)^2(x^2+x+1)^2(x^6+x^3+1)^2$ This one I mostly understand, aside from the $x^6$ factor, how could you know this was an irreducible polynomial in this field which out memorising them all? Or is that the technique..

Then, for $x^{15}-1$ I am told to assume that the primitive quartic polynomials in $\mathbb{F}_2[x]$ are $x^4+x+1$ and $x^4+x^3+1$.

I can check on wolfram alpha that the factorisation looks like: $x^{15}-1=(x+1)(x^2+x+1)(x^4+x+1)(x^4+x^3+1)(x^4+x^3+x^2+x+1)$

Now my hint suggested there are only $2$ quartic polynomials but this makes use of $3$...unless the $3$rd one is not primitive?

And also, how could one find this factorisation easily by hand? The one above I could attempt trial and error to find the irreducible polynomial of degree $6$ perhaps but for this one that seems a bit strange.

• Your polynomial $f(x)=x^4+x^3+1$ satisfies $f(x+1)=x^4+x^3+x^2+x+1$. – Sungjin Kim May 6 '18 at 0:32
• That last quartic is not primitive for it is a factor $x^5-1=(x-1)(x^4+x^3+x^2+x+1)$. – Jyrki Lahtonen May 6 '18 at 11:31

The finite field $\mathbb{F}_{p^n}$ is a splitting field of the polynomial $x^{p^n}-x$.
From this theorem, every element of $\mathbb{F}_{p^n}$ is a root of the polynomial $x^{p^n}-x$. We can apply this to $\mathbb{F}_{2^4}$ and $x^{2^4}-x$.
\begin{align} x^{2^4}-x&=x(x^{15}-1)\\ &=x(x-1)g(x) \end{align} where $g(x)$ contains factors $(x-\alpha)$ for each $\alpha\in\mathbb{F}_{2^4} \backslash \mathbb{F}_2$.
Since $\mathbb{F}_{2^4}$ contains $\mathbb{F}_{2^2}$, we consider an irreducible polynomial of degree $2$ over $\mathbb{F}_2$. Then $$g(x)=(x^2+x+1)h(x)$$ where $h(x)$ contains factors $(x-\alpha)$ for each $\alpha\in \mathbb{F}_{2^4}\backslash \mathbb{F}_{2^2}$. Each such $\alpha$ must be of degree $4$ over $\mathbb{F}_2$. Thus, $h(x)$ must contain an irreducible polynomial of degree $4$ over $\mathbb{F}_2$. Also, there are exactly three of them, $x^4+x^3+1$, $x^4+x+1$, and $x^4+x^3+x^2+x+1$. This gives the factorization $$x^{15}-1=(x+1)(x^2+x+1)(x^4+x^3+1)(x^4+x+1)(x^4+x^3+x^2+x+1).$$