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

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 WolframAlpha. Go there: http://www.wolframalpha.com/ and input "factor x^261" 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. 


I describe how to do this generally in my answer to question #16457 about cyclotomic integers. However, in this particular problem you are probably supposed to use the fact that the divisors of $x^{p^n}  x$ over $\mathbb{F}_p$ are precisely the irreducible polynomials of degree dividing $n$. 


This seems very much like homework to me, so I'll be brief. I assume that your $Z_p$ denotes the field with $p$ elements; I will call it $\mathbb{F}_p$ henceforth (lest it be confused with the ring $\mathbb{Z}_p$ of $p$adic integers). You want to factor the polynomial $X^{p^a1}1$ over $\mathbb{F}\_{p}$. Let us go into the field $\mathbb{F}_{p^a}$; what are the roots of the polynomial $X^{p^a1}1$ factor over there? Hence, which divisors does $X^{p^a1}1$ have over $\mathbb{F}_p$ ? Can any of them occur more than once? 

