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 ?