0
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ The inputs $a$, $b$, and $c$ are given in binary right? :) $\endgroup$
    – Michael Wehar
    Jun 15 '18 at 19:11
  • 1
    $\begingroup$ Yes, they are given in binary encoding... $\endgroup$
    – Frank Vega
    Jun 15 '18 at 19:18
  • 1
    $\begingroup$ 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 $\endgroup$
    – Frank Vega
    Jun 15 '18 at 19:20
  • 1
    $\begingroup$ Therefore, Prime Bounded Quadratic Congruence will be in NP-complete if and only if RP=NP. What do you think? $\endgroup$
    – Frank Vega
    Jun 15 '18 at 19:22
  • 2
    $\begingroup$ Yes, the problem is solvable in randomized polynomial time. So if you know this, what is the point of the question? $\endgroup$
    – Emil Jeřábek
    Jun 15 '18 at 22:34
1
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.