In finite fields, is there anything analogous to Sturm sequences for counting the number of roots of a polynomial in a given interval? Alternatively, showing that there are zero roots in a given interval would be almost as useful.
With Sturm sequences, the problem is that sign has no meaning in finite fields, so I don't know of a meaningful way to count sign changes.
The Fourier–Budan theorem seems to also rely on sign changes.
I didn't intend to post an answer to my own question, but Robert Israel's comment triggered an idea in my brain.
Here's a way to detect whether p(x) in a finite field has any roots in a given interval, or more generally in any given set of points.
All we need to do is to force any root in the interval to be a square, ie to have multiplicity at least two, and then detect squares.
So we precompute another polynomial r(x) that has exactly one root at each point of interest, and no roots elsewhere. Then we do square-finding on p(x)*r(x).
There is actually an analogy to Sturm sequences there, in that a common way to check for squares is to take the GCD of a polynomial and its derivative. But this is more efficient in that we don't need to compute signs or anything else on the remainders, we just check whether the result of GCD is a zero-degree polynomial or not.
This may not be an improvement over brute force, in that the degree of r(x) is just one less than the number of points we'd evaluate at to check by brute force. But if we have some freedom to choose our interval of interest, we can choose an interval such that r(x) and d r(x)/dx have some simple form, so there are grounds to hope that our work will be only proportional to the degree of p(x).
(Edit) I originally didn't think about false positives, because the above does what I need and my p(x) won't have roots with multiplicity. But it could give false positives when p(x) has some root outside the interval with multiplicity 2 or greater.
If that's a concern, you can detect squares on p(x) first, and then either remove the squares from p(x) or leave them and if the result of the GCD is the same as the known squares treat it as no root found.