# Bounded Quadratic Congruence Problem Variant (for some specific Residue)

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 ?

• 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. – Yuval Filmus Apr 11 '18 at 11:26
• thanks a lot. Would it be possible for you to help with a link/info for (a=1) case (and also $a$ = square) ? – J.Doe Apr 11 '18 at 11:31
• Take it as an exercise. – Yuval Filmus Apr 11 '18 at 11:32
• 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 ? – J.Doe Apr 11 '18 at 11:37
• This is unknown to me at the moment. – 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".