For a prime $N$, there are precisely $\frac{N-1}{2}$ quadratic nonresidues modulo $N$. Picking a base randomly, one would expect a $1/2$ chance of choosing a quadratic nonresidue. Excluding perfect squares, the expected chance would be slightly higher.
Utilizing quadratic reciprocity, one can reasonably quickly determine whether a randomly chosen base is a quadratic nonresidue, lets say with asymptotic complexity $O(Q)$.
It is also known that the smallest quadratic nonresidue is about less than $\sqrt{N}$, so choosing bases randomly one has worst case complexity of ${O}(\sqrt{N}Q)=\tilde{O}(\sqrt{N})$. However, the actual "chance" that this worst case occurs is astronomically small. This leads me to believe that it should be possible to get a better worst case runtime then $\tilde{O}(\sqrt{N})$.
Is there any deterministic runtime better than $\tilde{O}(\sqrt{N})$?
Note: Assuming the GRH, one knows that the smallest quadratic nonresidue is less than $ln^2(N)$ roughly, so assuming this we have ${O}(ln^2(N)Q)$. I am asking for a solution without assumption.
Quadratic residuosity (QR) and Quadratic non-residuosity (QNR) are both in NP$\cap$co-NP [1]. If you however think of QR as the problem of finding solutions to the congruence equation
$$x^2=a (\bmod b)$$
in the natural numbers, subject to the additional constraint that $x\le c$, then the problem becomes NP-complete [2]; the corresponding complementary problem is then complete in co-NP. But then, if the modulus is prime, this problem becomes a problem in P [3], assuming the truth of the extended Riemann hypothesis.
Caveat: The well known text on complexity by Arora and Barak has a mistake [4] in example 8.9 where it says that QNR is not known to be in NP.
[1] Cai, J. Y., and Threlfall, R., A note on quadratic residuosity and UP, Information Processing Letters 9-3 (2004) 127-131
[2] Manders K. L, and Adleman, L., NP-complete decision problems for binary quadratics, Journal of Computer and Systems Science 16, (1978), 168-184
[3] Garey, M., and and Johnson, D. S., Computers and Intractability: a Guide to the Theory of NP-completeness, Freeman and Company, (1979)
[4] Barak, B. personal communication 28 July 2023.