Factoring $x^{7} - 1$ into irreducibles over $\mathbb{F}_{2}[x]$

I know this breaks down into $(x - 1)(x^{6} + x^{5} + x^{4} + x^{3} + x^{2} + x +1)$, so the task is to show whether the second factor is irreducible over $\mathbb{F}_{2}[x]$. It's quick check that there are no roots, so one way might be to look at all remaining partitions of 6, then divide through by all polynomials of degree 4, 3 and 2. But there must be something faster.

• Remember that over $\mathbb{F}_2$ we have $1=-1$, you can finish now, should I write the details? – Yanko Jul 30 '17 at 20:14
• You only need to check for divisibility with degree $2$ or $3$ irreducible polynomials (divisibility by a degree $4$ implies divisibility by a degree $2$)...there aren't that many. – Kaj Hansen Jul 30 '17 at 20:19

Factoring $x^{7} - 1$ is equivalent to factoring $x^{8} - x$.
Now, $x^{8} - x=0$ is the equation that defines the finite field with $8$ elements.
Therefore, $x^{8} - x$ has at least one irreducible factor of degree $3$ (here we use that $8=2^3$).
This answer gives a simple argument that $x^3 + x^2 + 1$ and $x^3 + x + 1$ are the only irreducible polynomials of degree $3$ over $\mathbb{F}_{2}$. By the uniqueness of finite fields, both polynomials must divide $x^{8} - x$. Indeed, we can easily check that $x^{8} - x=x (x + 1) (x^3 + x + 1) (x^3 + x^2 + 1)$ and so $x^{7} - 1=(x + 1) (x^3 + x + 1) (x^3 + x^2 + 1)$.
We have $$x^6+x^5+x^4+x^3+x^2+x+1=(x^3+x^2+1)(x^3+x+1).$$ The cubic polynomials are irreducible over $\mathbb{F}_2$, since they do not have a root. To find this decomposition, one can start with a possible decomposition into two factors, either both of degree $3$, or one of degree $2$, and one of degree $4$, and solve the associated systems of equations in the coefficients. Another way is, to apply the Berlekamp algorithm.
Perhaps the "fastest" way is to search MSE for irreducible polynomials over $\mathbb{F}_2$, e.g., see here: