Clarification regarding Bounded Quadratic Congruence Problem Given: 3 positive integers $a, b, L$. 
Problem: Is there a positive integer $x &lt; L$ such that $x^2 \equiv \ a (mod\ b)$?  

The above problem is NP Complete (as mentioned in G&amp;J) even if we have the factorization of $b$ given. My query is the following: 

Suppose we have a promise/condition imposed that, the number of total occurrences of the residue $a$ is polynomially bounded w.r.t. number of prime factors in $b$, i.e. the number of occurrences of $a$ is always less than ${pct}^C$.

$pct$ = number of Prime factors of $b$ , $C$ = some positive integer constant.

Does this problem still remain NP-Complete or it becomes P time solvable.

Essentially, does the number of times a residue occurs is what makes this problem difficult or it doesn't matter and its just dependent on the number of prime factors in $b$?
The NP-completeness of the original problem was proved by Manders and Adleman [1] using a reduction from 3-SAT. Their reduction is parsimonious. Thus, (taking into account that the number of prime factors is upper bounded by the length of the input $n$, while in the M–A reduction, it is at least $n^\epsilon$) your problem is complete for promise-FewP. Note that by Valiant–Vazirani, already promise-UP is NP-hard under randomized polynomial-time reductions, hence the same holds for promise-FewP. Thus, the problem is essentially as difficult as NP.

EDIT: The answer above assumes that in the question, the unclear phrase “the number of occurrences of $a$” means the number of residues $x&lt;L$ such that $x^2\equiv a$. The OP indicates in a comment below that they rather intended it to mean the total number of residues mod $b$ that square to $a$. In the latter case, the problem is solvable in promise-ZPP: using the factorization of $b$, just compute all possible square roots of $a$ modulo $b$ by the usual algorithm (Tonelli–Shanks + Hensel’s lifting + Chinese remainder theorem).

Reference:

[1] Kenneth L. Manders and Leonard M. Adleman, NP-complete
  decision problems for binary quadratics, Journal of Computer and System
  Sciences 16 (1978), no. 2, pp. 168–184.