Factoring a polynomial modulo prime How would I go about factoring a polynomial $x^{5}-4$ over a finite field $\mathbb{F}_{29}=\mathbb{Z}/29\mathbb{Z}$? I know that $29$ is prime, so that will be relevant at the very least. Moreover, if we solve the equation $x^{5}\equiv 4 \mod 29$, we would get the solution $x=6$ unique up to modulo $29$. Is there a way to factor this over $\mathbb{Z}/29\mathbb{Z}$ by using the solution obtained from the equation?
 A: In finite fields, you have the advantage that given any $n \in \Bbb N$, there are only finitely many polynomials of degree $\le n$. In particular, there are only finitely many irreducible ones.
Now, in your example, you have already found a root of the polynomial. So, you can do the usual polynomial division to get $$x^5 - 4 = (x - 6)(x^4 + 6x^3 + 7x^2 + 13x + 20).$$
Now, you could check if $6$ is again a root of the quartic. This will not be the case. Since you already observed that the original polynomial has no root apart from $6$, you can conclude that the quartic has no root.
Thus, you have two cases now:

*

*The quartic is irreducible. (Meaning it has no proper factors.)

*The quartic is a product of two irreducible quadratics.

You could now try to list all (monic) irreducible quadratics over $\Bbb F_{29}$. These will be precisely those quadratics that have no root. Due to this, our life will be simpler.
(Note that this trick only works for quadratics and cubics. For higher degree polynomials, it may very well be the case that it is reducible but has no root.)
Of course, this is much easier to do by hand for the case of $\Bbb F_p$ with $p$ much smaller than $29$. In your case, there are $29^2 = 841$ monic quadratics. You would have to figure out which ones are irreducible. (You can note that $841 - 435  = 406$ would be irreducible.) It would probably be best to use some sort of program for this.
