Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How would I factor the above polynomial in this binary field? We just completed a course in Galois Theory, and I'm stuck on how to efficiently factor this polynomial. I tried considering computing all the irreducible polynomials of a certain degree in $\Bbb F_2$, but it is only $x^{256}-x$ in $\Bbb F_{2^8}[x]$ that is the product of all irreducible monic polynomials in the field, not the above polynomial in $\Bbb F_2$, so I'm really stuck. A tip as to the right direction to proceed would be a great answer.


I've realized that it is in fact the right choice to compute the number of monic irreducible polynomials of degree $d|n$ where $n = 256$. I will proceed from here.

Edit 2

My Answer

share|cite|improve this question
I just uploaded a picture of the answer I came up with, but thanks all for the help. – Moderat Apr 8 '13 at 20:18
up vote 2 down vote accepted

For a start, because $255=3\cdot 5 \cdot 17$ you have a difference of cubes, a difference of 5th powers and a difference of 17th powers. So you can divide out $\sum_{i=0}^k x^i$ for $k=2,4,16$ and $x-1$. In fact, feeding it to Alpha and ignoring the $\mathbb F_2$ gets factors with all coefficients $\pm 1$. It splits the rest into three factors.

share|cite|improve this answer
This approach is the one that my teacher hinted at for the test question (this is a question on a test that I did not get and am now trying to solve). Can you elaborate on how we know that $\sum_{i = 0}^k x^i$ for $k = 2,4,16$ divides $x^{255}-1$? – Moderat Apr 2 '13 at 2:48
@JJR: My motivation was that you can factor $x^3-1$ as $(x-1)(x^2+x+1)$ and similarly for any power of $x$. As $255$ is a multiple of $3$ you can write this as $(x^3)^{85}-1$,which gives you the factor $(x^{3}-1).$ Similarly for $5,17$ – Ross Millikan Apr 2 '13 at 2:55
I ended up figuring out how to go about this problem, I will post my solution shortly – Moderat Apr 8 '13 at 20:11

Hint: $x^{2^n}-x$ is the product of all monic primes in $\mathbb F_2[x]$ of degree $d|n$.

Then $x^{2^8}-x = x^{256}-x = x(x^{255}-1)$.

share|cite|improve this answer
Ah! I read the Proposition wrongly, and the monic primes are indeed in $\Bbb F_2[x]$, I was under the wrong impression as you can see from my wording in the question. Thank you! – Moderat Apr 2 '13 at 2:44

Your Answer


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.