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?

  • 2
    $\begingroup$ $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$. $\endgroup$ – Thomas Andrews May 11 '15 at 21:45
  • $\begingroup$ See also here $\endgroup$ – Count Iblis May 11 '15 at 21:50
  • $\begingroup$ @ThomasAndrews Could you link me to a proof of that, please? $\endgroup$ – James May 11 '15 at 22:00
  • 1
    $\begingroup$ @James math.stackexchange.com/questions/1241931/… $\endgroup$ – user26857 May 20 '15 at 9:31

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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