Efficiency of general solution to "primes of the form $x^2+ny^2$"

Question

Cox's book Primes of the form $x^2+ny^2$ presents a general solution to the question "for a (fixed $n>0$ and) given prime $p$, does $p=x^2+ny^2$ have an integer solution?". The general solution is "there is an integer polynomial $f_n$ such that $p=x^2+ny^2$ iff (some side conditions hold and) $f_n(x)=0$ has a solution mod $p$".

I am concerned that the condition on the RHS isn't any easier to verify than the one on the LHS, and hence that this isn't a "solution" to the problem at all.

1. Note that in checking whether $p=x^2+ny^2$ has a solution, we know that $\left|x\right|,\left|y\right|<\sqrt p$, hence, at worst, we need to check about $(2\sqrt{p})^2=4p$ values of $(x,y)$.

   However, in checking whether $f_n(x)=0\mod p$ has a solution, we need to check all $p$ values of $x$, so this is at best a factor of $4$ improvement, which isn't much (and may well be worse than that, since $f_n$ could be a more complicated polynomial to compute that $x^2+ny^2$).

2. By contrast, in Fermat's original theorem (where $n=1$), the condition is just $p=1\mod 4$, which is obviously much faster to check. Similarly, in the other cases presented near the beginning of the book, the solution is given in terms of congruence conditions on $p$.

3. In these simplest cases (when the class number $h(-4n)$ is $1$), these congruence conditions come from quadratic reciprocity: one first derives the condition that $D$ is a square mod $p$, and then quadratic reciprocity lets us reformulate this in terms of congruence conditions on $p$.

   Hence, I could imagine that (at least for some $n$), there is some "reciprocity law" allowing us to check whether $f_n=0\mod p$ has a solution in terms of congruence conditions on $p$, which would be an improvement. Is this what's going on?

4. Note that toward the end of the book, Cox discusses an algorithm to solve the problem. But as far as I can tell, this is just an algorithm to find $f_n$, not to solve $f_n(x)=0\mod p$. (And anyway, there is obviously an algorithm to solve $f_n(x)=0\mod p$; the issue at hand is whether there is an efficient algorithm.

I apologize if the answer to this question is already contained in Cox's book. I haven't read it in detail.