Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
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$. –  André Nicolas Jul 12 '11 at 7:16

2 Answers 2

up vote 13 down vote accepted

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.

share|improve this answer

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,

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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