3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Remember that over $\mathbb{F}_2$ we have $1=-1$, you can finish now, should I write the details? $\endgroup$ – Yanko Jul 30 '17 at 20:14
  • $\begingroup$ 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. $\endgroup$ – Kaj Hansen Jul 30 '17 at 20:19
4
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ This is the answer I would have given. $\endgroup$ – Lubin Jul 31 '17 at 1:12
3
$\begingroup$

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:

Find all irreducible monic polynomials in $\mathbb{Z}/(2)[x]$ with degree equal or less than 5.

$\endgroup$

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.