# Is Prime Bounded Quadratic Congruence NP-complete?

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].

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.

• The inputs $a$, $b$, and $c$ are given in binary right? :) – Michael Wehar Jun 15 '18 at 19:11
• Yes, they are given in binary encoding... – Frank Vega Jun 15 '18 at 19:18
• Michael Wehar, I think this problem could be solved in randomized polynomial time. Look at this:en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm – Frank Vega Jun 15 '18 at 19:20
• Therefore, Prime Bounded Quadratic Congruence will be in NP-complete if and only if RP=NP. What do you think? – Frank Vega Jun 15 '18 at 19:22
• Yes, the problem is solvable in randomized polynomial time. So if you know this, what is the point of the question? – Emil Jeřábek supports Monica Jun 15 '18 at 22:34