Bounded Quadratic Congruence Problem Variant (for square Residue) This is a follow up to the following question: Bounded Quadratic Congruence Problem Variant (for some specific Residue)

As indicated that for square residue the problem is solvable in polynomial time. Let us consider a modified version of the same problem:

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

where $M$ is some positive integer constant, $a$ is a residue that is also a square. 

Can the same approach be used to solve this slightly modified problem easily? It seems so but I am not sure.
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.