In number theory, an integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n; i.e., if there exists an integer x such that:$$    x^2\equiv q \pmod{n}. $$Otherwise, q is called a quadratic nonresidue modulo n.Problem Definition: Given a constant c, is there a positive integer x < c such that $$    x^2\equiv q \pmod{n}. $$If n is composite, the problem is NP-Complete, even if given the prime factorization of n. But, if n is a prime the problem is solvable in polynomial time. Query: In case n is composite, and given that it has lets say exactly 3 distinct prime factors, does the problem still remain NP-Complete? Any link to the references?
A Query regarding Quadratic Residuocity Problem
complexity theory;np complete