# Factoring $x^{255} -1$ over $\Bbb F_2$

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.

### Edit

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

-
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

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.

-
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)$.

-
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