How to factor polynomials in $\mathbb{Z}_n$?

Question

How to factor a certain polynomial over $Zn$.

for example factor the following polynomial into irreducible polynomials in $Z5$:

$X^3+X^2+X-1$

or factor the following polynomial into irreducible polynomials in $Z2$:

$X^4+X+1$

is there a certain method (algorithm) I can follow?

Please help I'm stuck and i really need the help!

thank you in advance!!

Answer 1

The first one is easily proven to be irreducible since a polynomial of degree $\;\le 3\;$ is reducible over some field iff it has a root in that field.

For the second one observe that

$$x^4+x^2+1=(x^2+x+1)^2\in\Bbb F_2[x]$$

Answer 2

let $ f $ be a irreducible polynomial over finite field $\Bbb{F}_q$ and $ \alpha$ is a zero of $f$. let $ d=\mathrm{deg}(f)$. then degree of $\Bbb{F}_q(\alpha)$ is $d$ and the zero is also zero of $ x^{q^d}-x$. therefore all irreducible polynomial with degree $d$ is factor of $x^{q^d}-x$. If $f$ is not a factor of $x^{q^d}-x$, then $f$ is reducible.