Bounded Quadratic Congruence Problem Variant (for square Residue)

Question

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<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.

Answer 1

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<L$. As you previously noted, the latter problem is NP-complete.