How do I factorize a polynomial $X^n - 1$ over $\mathbb{F}\_p$? In particular I need to find factors of the polynomial $X^{3^3 - 1} - 1 = X^{26} - 1$ over $\mathbb{F}\_3$.



How to factorize X^n - 1 in Z/pZ?
If you just need a quick answer (to decide if something else is going to work how you need), then you can do this with Wolfram|Alpha. Go there:
 <http://www.wolframalpha.com/>
and input "factor x^26-1" and press the "equal" button. It'll show some info about the polynomial, including the factors mod 2. In many boxes, there's a link for "Show More". Press the one attached to the factors over GF(2), and it'll show you the factors over GF(3). In this case, you get
 $$(x+1) (x+2) (x^3+2 x+1) (x^3+2 x+2) (x^3+x^2+2) (x^3+x^2+x+2) (x^3+x^2+2 x+1) (x^3+2 x^2+1) (x^3+2 x^2+x+1) (x^3+2 x^2+2 x+2).$$


Annoying to have "2" instead of "-1" in GF(3), but that's the price of having a machine do your work for you.


