Determine if a polynomial on a finite field is separable

Question

If I want to determine if a given polynomial $P$ over a finite field $\mathbb{F}_q$ is separable, what are the possibilities ? I mean :

• What is the general method ? I think it's to compute the GCD of $P$ and $P'$ with the Euclid algorithm, but I'm not sure.
• Is there any situations where tips can get the result faster ?

[Bonus] And for $k = \mathbb{Q}$ ?

Answer 1

Too long for a comment:

Any polynomial is separable over a field of characteristic zero, but be careful: this means that all the roots of the polynomial's irreducible factors are simple.

In case the characteristic is positive, say $\,p\,$ , we have that a polynomial $\,f(x)\,$ is not separable iff there exists another (separable) polynomial $\,g(x)\,$ over the same field s.t. $\,f(x)=g(x^{p^n})\,\,,\,\,n\in\Bbb N$

Answer 2

In any field, is $p(x)$ has repeated roots then it shares them with $p'(x)$, its (formal) derivative. So the GCD you mention helps weeding out multiple roots, but not to show if the polynomial is irreducible. If it is up to a quintic, checking that it has no linear or quadratic factors (by long division, and looking if some combination of coefficients give zero remainder) answers the question definitely, for higher degrees it gets messy...

Most computer algebra packages include efficient techniques to factor polynomials, perhaps take a trip through them. The (sadly unfinished) "Computation in Finite Fields" by John Kerl might be of help.