I just asked wolframalpha to factor $X^{16}+X$ over $\mathbb{F}_2$. The normal factorization is $$ X(X+1)(X^2-X+1)(X^4-X^3+X^2-X+1)(X^8+X^7-X^5-X^4-X^3+X+1) $$ and over $GF(2)$ it is $$ X(X+1)(X^2+X+1)(X^4+X+1)(X^4+X^3+1)(X^4+X^3+X^2+X+1). $$ Does the second form follow from the first, or is there a different way to factor over $\mathbb{F}_2$? I noticed that simply replacing the $-$ signs with $+$ signs in the first factorization doesn't yield the second one.

  • 3
    $\begingroup$ The last term of the first is (mod $2$) the product of the $4$th and $5$th term of the second. The first $4$ terms of the first were irreducible mod $2$. $\endgroup$ – André Nicolas Jul 12 '11 at 7:16

It shouldn't be a surprise that switching from integer (or rational) coefficients to modular coefficients allows for further factorization. The simplest example is probably the factorization $$ x^2+1=x^2+2x+1=(x+1)^2 $$ over $F_2$.

Here the key difference between the two factorizations is that the polynomial of degree 8 splits into a product of two quartic polynomials over $F_2$: $$(x^4+x+1)(x^4+x^3+1)=x^8+x^7+x^5+x^4+x^3+x+1$$ that is equal to (up to sign changes) your last factor.

Once you start on finite fields in your studies you will immediately learn that all the elements of $GF(16)$ are roots of the polynomial $x^{16}+x$. As that field is a degree 4 extension of $F_2$, all those elements have minimal polynomials of degree a factor of 4. Furthermore, all such irreducible polynomials appear as factors of $x^{16}+x$. Now, we easily see that both $x^4+x+1$ and its reciprocal polynomial $x^4+x^3+1$ are both irreducible in the ring $F_2[x]$, so they must appear as factors.

  • $\begingroup$ In $\mathbb{F}_2[x]$, why can't we just factor $x^{16}-x=x(x+1)$? It seems to me that $x$ and $(x+1)$ should be irreducible since they have degree 1. $\endgroup$ – Pascal's Wager Feb 28 '18 at 20:12
  • $\begingroup$ @Pascal'sWager Yes, $x$ and $x+1$ are both irreducible. But their product has degree two whereas $x^{16}-x$ has degree $16$. In other words $x^{16}-x\neq x(x+1)$, Why did you think this would be a factorization? $\endgroup$ – Jyrki Lahtonen Feb 28 '18 at 20:17
  • $\begingroup$ I thought it would be a factorization since $x^{16}-x=x(x+1)$ for any $x \in \mathbb{F}_2$. $\endgroup$ – Pascal's Wager Feb 28 '18 at 20:31
  • $\begingroup$ @Pascal'sWager But we are dealing with formal polynomials here. Not polynomial functions. In other words, you should not think of $x$ as a variable ranging over $\Bbb{F}_2$. It is an indeterminate. You may want to study this thread. $\endgroup$ – Jyrki Lahtonen Feb 28 '18 at 20:37

The second form does follow from the first. Note that over $\mathbb F_2$, the pair of polynomials $$ X^2 - X + 1 \quad \text{ and } \quad X^2 + X + 1 $$ and the other pair $$ X^4 - X^3 + X^2 - X + 1 \quad \text{ and } \quad X^4 + X^3 + X^2 + X + 1 $$ are the same. The only difference that comes up in $\mathbb F_2$ is that the polynomial of degree $8$ factors.

Hope that helps,


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.