How is a polynomial like $x^5-1$ be factorised in a prime field like $\mathbb{F}_{11}$ for example ? Any advice ?
I was successful in trying all members of $\mathbb{F}_{11}$ to find the roots as described in the answers. Thanks. But I wasn't successful to do the same in $\mathbb{F}_{19}$. and I can't understand why.
On
There are specialists in this kind of thing, and I am not one of them. But let me say a few things that may help.
First, if the degree of the polynomial is not too big, or if the prime is not too big, the problems are surmountable. I don’t know how I would attack a degree-$1000$ polynomial over $\Bbb F_{1009}$, however, though I might try these tricks:
You certainly want to look for roots. If you’re not in a mood to try all the elements of $\Bbb F_p$, you can try finding the gcd of your polynomial with the polynomial $x^p-x$, because this is the product of all polynomials of form $x-a$ with $a\in\Bbb F_p$. If the gcd is not $1$, it will be the product of all the monic linears, so you really have the roots in hand.
Similarly, if there are no roots, then you might look at $(x^{p^2}-x)/(x^p-x)$. This is the product of all the irreducible monic quadratic polynomials over $\Bbb F_p$. Again, take the gcd of this with your original polynomial, and again, if the gcd is not $1$, then it will be the product of all quadratic factors of your polynomial. You might try this with a random quartic over $\Bbb F_p$ for a prime that’s not too large, and see how it works out.
Over any field:
$$x^5-1=(x-1)(x^4+x^3+x^2+x+1)$$
But over the field $\;\Bbb F_{11}\;$ :
$$3^2=9=-2\pmod{11}\implies 3^5=\left(3^2\right)^2\cdot3=(-2)^2\cdot3=4\cdot3=1\pmod{11}\implies$$
$$3^5=1\pmod{11}$$
and also $\;5^2=9=(-2)\implies 5^5=1\;$
and you already have three different roots, so you can factor out a quadratic:
$$x^5-1=(x-1)(x-3)(x-5)(x^2+9x+3)\pmod{11}$$
Now check the above quadratic's discriminant is $\;3\;$ , which is a square, and you can continue factoring.