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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.