# 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?

• $x^{p^n}-x\in\mathbb Z_p[x]$ is the product of all prime polynomials with degree dividing $n$. In this $x^{16}-x=x(x^{15}-1)$ is the product of all prime polynomials of degree $1,2$ and $4$. – Thomas Andrews May 11 '15 at 21:45
• See also here – Count Iblis May 11 '15 at 21:50
• @ThomasAndrews Could you link me to a proof of that, please? – James May 11 '15 at 22:00
• – user26857 May 20 '15 at 9:31

Well, it's enough to consider factors of degree $\le \deg(p)/2$.