This question already has an answer here:

I'm trying to factor $x^6+x^5+x^4+x^3+x^2+x+1$ in $\mathbb{F}_2[x]$. But I don't know how to do that. Anyone can tell whether there is a nice way to solve all these kinds of problems?


marked as duplicate by Ben West, Community Apr 29 '16 at 2:27

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ you mean in $\mathbb{F}_2[x]$ ? $\endgroup$ – reuns Apr 29 '16 at 2:12
  • $\begingroup$ Think about powers mod 2, and you can simplify this a bunch. $\endgroup$ – Davey Apr 29 '16 at 2:12
  • $\begingroup$ wiki/Factorization_of_polynomials_over_finite_fields $\endgroup$ – reuns Apr 29 '16 at 2:16
  • $\begingroup$ Both 0 and 1 are not root, seems like this polynomial is irreducible. But I'm not sure. $\endgroup$ – Kelan Apr 29 '16 at 2:17
  • 1
    $\begingroup$ and since it is of degree $6$ all you have to do is proving it is not divisible by any degree $2$ and $3$ polynomial : $\endgroup$ – reuns Apr 29 '16 at 2:18

Well, in general, one usually recursively builds irreducible polynomials of low degree via Euclidean division. But in this case, there is a very nice trick: let $P(X) = X^6+X^5+X^4+X^3+X^2+X+1$. Then it is not hard to show that $P(X)(X+1) = X^7+1$ (one can either compute this directly, or think of the analagous result for truncated geometric series). But then $P(X)(X+1)(X) = X^8+X = X^{2^3}+X$, which is the product of all irreducible polynomials of degree dividing $3$ over $\mathbb{F}_{2}$. So $P(X)$ must factor as the product of the unique two irreducible polynomials of degree $3$ over $\mathbb{F}_{2}$. I leave it to you to compute these; feel free to comment if you need more help.

  • $\begingroup$ I don't see the "all irreducible polynomials of degree dividing 3" trick, where does it come from ? $\endgroup$ – reuns Apr 29 '16 at 2:20
  • $\begingroup$ This is a classical and very general result: the polynomial $X^{p^{n}} - X$ is always the product of all irreducible polynomials of degree dividing $n$ over the field $\mathbb{F}_{p}$. There are many resources for this particular result, including some on this site. $\endgroup$ – Alex Wertheim Apr 29 '16 at 2:22
  • $\begingroup$ ok, I didn't find a name but there is those proofs math.stackexchange.com/questions/106721/… $\endgroup$ – reuns Apr 29 '16 at 2:25

Not the answer you're looking for? Browse other questions tagged or ask your own question.