Bounded Quadratic Congruence Problem Variant (for square Residue)
The problem is NP-complete.  Let $d = \gcd(M,b)$.  If $a$ is not a multiple of $d$, then there is no solution.  Otherwise, let $a' = a/d$ and $B = b/d$ and $c = M/d$ and $A \equiv a' c^{-2} \pmod B$.  Then the original equation has a solution if and only if $x^2 \equiv A \pmod B$ has a solution with $x&lt;L$.  As you previously noted, the latter problem is NP-complete.