How i can reduce this polynomial in $\mathbb{Z}_2 [x]$?

Question

How i can reduce the polynomial $f(x) = x^9+x^8+x^6+x^5+x^4+x^3+1 \in \mathbb{Z}_2 [x]$. I've tried use the reduction modulo a prime, but that don't solve the problem totally.

Answer 1

Using sage the factorization is easy:

sage: R.<x> = PolynomialRing(GF(2))
sage: f = x^9 + x^8 + x^6 + x^5 + x^4 + x^3 + 1
sage: f.factor()
(x^3 + x^2 + 1) * (x^3 + x + 1)^2

(Assuming that "reduce" means "factor" in the OP.) Manually, as a human, we expect factors - if any - till degree four. So it is a good try to see if one of the factors

• $x$, $(x+1)$,
• then $(x^2+x+1)$, the only irreducible polynomial in degree two,
• then $(x^3+x+1)$, $(x^3+x^2+1)$, the only irreducible polynomials in degree three,
• and finally $(x^4 + x + 1)$, $(x^4 + x^3 + 1)$, $(x^4 + x^3 + x^2 + x + 1)$, the only irreducible polynomials in degree four

divides the given polynomial.