Test if a polynomial is a square

Question

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$.

Answer 1

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.