Is Prime Bounded Quadratic Congruence NP-complete?
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...