Bounded Quadratic Congruence:
Instance: Three positive integers $a$, $b$ and $c$.
Question: Is there a positive integer $x<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<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.