Is Prime Bounded Quadratic Congruence NP-complete? Bounded Quadratic Congruence:

Instance: Three positive integers $a$, $b$ and $c$. 

Question: Is there a positive integer $x&lt;c$ such that $x^{2} \equiv a \, (mod \ b)$?

Bounded Quadratic Congruence is $NP$-$complete$ [1].

Prime Bounded Quadratic Congruence:

Instance: Three positive integers $a$, $b$ and $c$ such that $b$ is a prime number. 

Question: Is there a positive integer $x&lt;c$ such that $x^{2} \equiv a \, (mod \ b)$?

Is this problem $NP$-$complete$ as well?

Reference:

[1] Kenneth L. Manders and Leonard M. Adleman, NP-complete decision problems for binary quadratics, Journal of Computer and System Sciences 16 (1978), no. 2, pp. 168–184.
This problem can be solved in randomized polynomial time. Look at this:

https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm

Therefore, if Prime Bounded Quadratic Congruence would be in NP-complete, then RP = NP. 

Consequently, the answer of this question is an outstanding problem in complexity theory, so it is not worth to ask it here...