The Quadratic Congruences problem asks if for constants $a$, $b$, and $c$, does there exist $x$ such that $x<c$ and $x^2 \equiv a\mod b$?
This problem is known to be NP-complete. However I can't find anywhere which states what is $n$ such that this is verifiable in polynomial time as $n$ varies? I presume it's the value of $b$?
However it seems to me that this is trivially solvable in polynomial time - just check every number between $0$ and $c$. Since each number can be checked in polynomial time, this is doable in polynomial time.
What am I missing here? Is it that $x$ can be negative too? But if so $-x^2=x^2$ so isn't this question identical to whether there exist $x$ such that $x^2 \equiv a\mod b$ irrespective of $c$?
I notice I'm confused here so I'm hoping someone can help point me in the right direction.
In this context, the relevant $n$ is the length of the input. So $n$ will scale like the logarithm of the input, so that your solution has actually exponential complexity.