Test if a polynomial is a square Let $F_q$ be a finite field. What is the best algorithm to test if a polynomial $f$ is a square? I am only interested in the regime q small respect to the degree of $f$.
 A: Compute $g = f/\gcd(f, f')$, then (recursively) determine whether $h = f / g^2$ is a square.
If $f$ is a square, then all of its roots occur with even multiplicity, so it has a nontrivial $\gcd$ with its derivative.  Then $g$ has roots which are the repeated roots of $f$ with their multiplicities reduced to $1$.  Then $h$ is $f$ with all the multiplicities of its repeated roots reduced by $2$.  Iterating, we get a sequence of $h$s, $h_1, h_2, \dots h_k$, which terminates when $2k \geq \deg f$ (i.e., when $\gcd(f,f') = 1$) because the multiplicities of the roots of $f$ are finite.  If $h_k$ is a constant, then $h_{k-1}$ is a square, and so on, rolling back up to $f$ is a square.  If $h_k$ is not a constant, then $h_{k-1}$ is not a square, and so on, rolling back up to $f$ is not a square.
This is adapted from the usual first step of factoring polynomials, reduction to square-free form.  See here for more on this step.

Added in edit:
One way to detect that $h$ is not a square polynomial is that $h$ is not a polynomial.  That is $g^2 \nmid f$.  (Our way of constructing $g$ ensures this can't happen here, but it is a thing which can happen in more general settings.)
Note that this is "complicated" in characteristic $2$.  I put that in quotes because every element is a square in characteristic $2$ (because the Frobenius map is surjective in finite fields), so a much easier algorithm in characteristic $2$ is return True.(Not quite that easy, but still easy.)

Knuth (Art of Computer Programming, Vol. 2, p. 446) analyzes Berlekamp's algorithm modulo a prime $p$.  The first step of Berlekamp's algorithm, "step B1", computes $\gcd(f,f')$ in $O(n^2)$ time.  For large $q$, replace this with $O(n^2 (\log q)^2)$ to account for time computing inverses in $\mathbb{F}_q$ (by any of several methods).  Here, $n = \deg f$.  The algorithm above has at most $\deg f/2$ $\gcd$s, so would seem to be $O(n^3)$ for your case of small $q$.
Wikipedia suggests that Berlekamp's algorithm and the Cantor-Zassenhaus algorithm are the go-to algorithms for factoring over finite fields.  Both rely on $\gcd$s, so I don't see that there are evident alternatives to the algorithm above.
There are some sneaky algorithms for factoring modulo primes, $p$, having $p-1$ smooth (i.e., factoring into small numbers).  See Factoring polynomials modulo special primes.  I'm not familiar with these methods.
