<p>This problem can be solved in randomized polynomial time. Look at this:</p>

<p><a href="https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm</a></p>

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

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

CC BY-SA 4.0
2018-06-18T13:11:41.840Z
2018-06-18T13:11:41.840Z
Frank Vega
<p><strong>Bounded Quadratic Congruence:</strong></p>

<p>Instance: Three positive integers $a$, $b$ and $c$. </p>

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

<p>Bounded Quadratic Congruence is $NP$-$complete$ [1].</p>

<p><strong>Prime Bounded Quadratic Congruence:</strong></p>

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

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

<p>Is this problem $NP$-$complete$ as well?</p>

<p><strong>Reference:</strong></p>

<p>[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.</p>

CC BY-SA 4.0
2018-06-15T19:11:05.883Z
The inputs $a$, $b$, and $c$ are given in binary right?  :)
Michael Wehar
CC BY-SA 4.0
2018-06-15T19:18:32.940Z
Yes, they are given in binary encoding...
Frank Vega
CC BY-SA 4.0
2018-06-15T19:20:45.153Z
Michael Wehar, I think this problem could be solved in randomized polynomial time. Look at this:https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm
Frank Vega
CC BY-SA 4.0
2018-06-15T19:22:46.510Z
Therefore, Prime Bounded Quadratic Congruence will be in NP-complete if and only if RP=NP. What do you think?
Frank Vega
CC BY-SA 4.0
2018-06-15T20:55:40.017Z
Thanks for sharing the link!!  Well I don't know how your randomized polynomial time algorithm works.  But, I think this is a neat approach and idea.  :)
Michael Wehar
CC BY-SA 4.0
2018-06-15T22:34:29.237Z
Yes, the problem is solvable in randomized polynomial time. So if you know this, what is the point of the question?
Emil Jeřábek
CC BY-SA 4.0
2018-06-21T14:46:50.907Z
Emil Jeřábek, there is something wrong here!!! If we find a solution for a prime, then we can find a solution for the power of this prime using the Hensel's lemma:https://en.wikipedia.org/wiki/Hensel%27s_lemma. And if you can find the solution for a prime power then you can find the solution to the Bounded Quadratic Congruence problem using the Chinese remainder theorem:https://en.wikipedia.org/wiki/Chinese_remainder_theorem. What do you think?
Frank Vega
CC BY-SA 4.0
2018-06-21T15:45:28.777Z
The number of solutions of $x^2\equiv a\pmod b$ is exponential in the number of distinct prime factors of $b$, and there is no shortcut how to check if some of them is below $c$ other than by generating all of them. So this only gives you an exponential-time algorithm. And of course, you need first to have the prime factorization of $b$, which is itself not a light assumption. (This is, however, not actually important, as Manders and Adleman also show NP-completeness of the problem when the full factorization of $b$ is given as input.)
Emil Jeřábek
<cc.complexity-theory><complexity-classes><np-complete>
Is Prime Bounded Quadratic Congruence NP-complete?
Frank Vega
# Is Prime Bounded Quadratic Congruence NP-complete?

(Asked by: username_0 on 2018-06-15)

**Bounded Quadratic Congruence:**

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

Question: Is there a positive integer $x

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

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.

**Tags:** cc.complexity-theory, complexity-classes, np-complete

> **Comments:**
> **username_1**: The inputs $a$, $b$, and $c$ are given in binary right?  :)  
> **username_0**: Yes, they are given in binary encoding...  
> **username_0**: username_1, I think this problem could be solved in randomized polynomial time. Look at this:https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm  
> **username_0**: Therefore, Prime Bounded Quadratic Congruence will be in NP-complete if and only if RP=NP. What do you think?  
> **username_1**: Thanks for sharing the link!!  Well I don't know how your randomized polynomial time algorithm works.  But, I think this is a neat approach and idea.  :)  
> **username_2**: Yes, the problem is solvable in randomized polynomial time. So if you know this, what is the point of the question?  
> **username_0**: username_2, there is something wrong here!!! If we find a solution for a prime, then we can find a solution for the power of this prime using the Hensel's lemma:https://en.wikipedia.org/wiki/Hensel%27s_lemma. And if you can find the solution for a prime power then you can find the solution to the Bounded Quadratic Congruence problem using the Chinese remainder theorem:https://en.wikipedia.org/wiki/Chinese_remainder_theorem. What do you think?  
> **username_2**: The number of solutions of $x^2\equiv a\pmod b$ is exponential in the number of distinct prime factors of $b$, and there is no shortcut how to check if some of them is below $c$ other than by generating all of them. So this only gives you an exponential-time algorithm. And of course, you need first to have the prime factorization of $b$, which is itself not a light assumption. (This is, however, not actually important, as Manders and Adleman also show NP-completeness of the problem when the full factorization of $b$ is given as input.)  

---

## 1 answers

### Answer by username_0 on 2018-06-18. Score: 1 | Accepted answer

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


---

