Methods for factorising polynomials into irreducibles over finite fields I was given a problem recently, part of whose solution was to factorise $x^{15}+1$ in $\mathbb F_2[x]$. It turns out that the factorisation is $$(x+1)(x^2+x+1)(x^4+x^3+x^2+x+1)(x^4+x+1)(x^4+x^3+1),$$ but this took me a very long time to find, and I expect a lot longer than it should have. Therefore my question is

What are good techniques for factorising polynomials in finite fields? And when I partially factorise a polynomial, how can I tell if the factors I have are irreducible?

What I know:
The Frobenius homomorphism can help in some obvious situations like $$x^8-1=x^{2^3}-1^{2^3}=(x-1)^{2^3}=(x+1)^8$$ in $\mathbb F_2[x].$ Is this useful in more exotic situations?
For degree 2 or 3 polynomials, checking irreducibility is the same as checking there are no roots. For $p(x)$ of degree larger than 3, do I just have to check that no irreducible polynomial of degree less than $\deg (p)$ divides it or is there a better way?  

Well, it's enough to consider factors of degree $\le \deg(p)/2$.
Theoretically, the algorithms to use are Cantor-Zassenhaus and Berlekamp's.  However, I don't think you'd want to try either of these by hand.
