Given: 3 positive integers $a,b,L$. Problem: Is there a positive integer $x<L$ such that $x^2≡ a(mod\ b)$?

The above problem is NPComplete (as mentioned in G&J) even if we have the factorization of $b$ given. My query is the following:

Is there some specific value of $a$ (say $a_0$) such that, if we limit the original problem (the residue) to only $a_0$, the problem ceases to be NPComplete (and much easily solvable than the generic case) ?

My guess is for any/each specific $a_0$ the problem still remains NPComplete but I am not certain. Anyone please ?

  • 2
    $\begingroup$ The problem becomes easy when $a=0$ or $a=1$, and (I believe) when $a$ is a square. So the real question is whether there exists a value of $a$ for which the problem remains NP-complete. $\endgroup$ – Yuval Filmus Apr 11 '18 at 11:26
  • $\begingroup$ thanks a lot. Would it be possible for you to help with a link/info for (a=1) case (and also $a$ = square) ? $\endgroup$ – J.Doe Apr 11 '18 at 11:31
  • $\begingroup$ Take it as an exercise. $\endgroup$ – Yuval Filmus Apr 11 '18 at 11:32
  • $\begingroup$ I will try. "So the real question is whether there exists a value of a for which the problem remains NP-complete". I was going to follow up with the exact same question :), but I am guessing this is still unknown ? $\endgroup$ – J.Doe Apr 11 '18 at 11:37
  • $\begingroup$ This is unknown to me at the moment. $\endgroup$ – Yuval Filmus Apr 11 '18 at 11:38

Yes. If $a=1$, the problem is no longer NP-complete; the answer to the problem is always "yes, there is such a positive integer".

| cite | improve this answer | |

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.