TITLE: How to factorise a polynomial in the ring $\mathbb{Z}_p[x]$
QUESTION [5 upvotes]: I previously asked a question: How is $x^2 + x + 1$ reducible in $\mathbb{Z}_3[x]$?, and I got told there that you could factorise $x^2 + x + 1 = (x + 2)(x+2) = (x-1)(x-1)$ in the ring $\mathbb{Z}_3[x]$ and I understand why. 
What I want to know is:

If I am given a polynomial, lets say $x^2 + x + 1$, what sort of stuff am I looking for to factorise it?
Does this change is it is a polynomial of a higher order (say something like $x^4 - 1$ (that's the question I have to solve, please don't give an answer for it).
As the ring is $\mathbb{Z}_p[x]$, do I only look for the $x$ coefficiant to be $\mod p$ or do I look at all coefficiants?
Will there be a finite number of solutions?
Is there a method to factorise (i,e quadratic formula) or do I just have to notice the form of the polynomial?

EDIT: In my example, if I want to factorise $x^2 + x + 1$ in the ring $\mathbb{Z}_3[x]$, do I want to find polynomials where I have $[1]x^2 + [1]x + [1]$ where the $[a]$ is the equivalence relation (if thats the right word?) $a \mod p$, so in this case it would be $1 \mod 3$?

REPLY [5 votes]: Quadratic polynomials can be factored by using the quadratic formula to find their roots (except in characteristic 2, where things are trickier).
Cubic polynomials can be factored by using the cubic formula to find their roots (except in characteristic 2 or 3, where things are trickier). Of course, just like in the rationals, this is painful (albeit less so, IMO). Many times you can identify a root, though, in which case you can factor out the linear factor.
For some special polynomials, identifying the roots (in the algebraic closure) as being of a special form can be very useful if you can relate them to structural things like norms or traces or roots of unity.
There are general methods to factor. One of the main steps is to use the fact that the roots of $ x^q - x$ are all of the elements of $\mathbf{F}_q$. So, for example, you can find the product of all distinct linear factors of a polynomial $f(x)$ over $\mathbf{F}_p$ by computing
$$ \gcd(x^p - x, f(x)) $$
This is useful, because one can efficiently compute modular exponentiation
$$ x^p \pmod{f(x)} $$
to get a gigantic short-cut on the first step of the Euclidean algorithm.
Similarly, the product of all quadratic and linear factors is given by
$$ \gcd(x^{p^2} - x, f(x)) $$
(because the roots of an irreducible quadratic over $\mathbf{F}_p$ are elements of $\mathbf{F}_{p^2}$)
Doing these calculations is called "distinct-degree factorization". The next step in a typical general factorization algorithm is "equal-degree factorization".
{"set_name": "stack_exchange", "score": 5, "question_id": 361493}