Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

For an integer $m$, let $S^m_{x_0,x_1} = \{ t | x_0 ≤ t ≤ x_1 $ and $t$ is a square modulo $m \}$. Let $S^m_x$ = $S^m_{0,x}$.

Determining whether the sets $S^m_x$ are empty is easy (1 is always a square, you decide whether 0 is too).

What is the computational complexity to determine the size of $S^m_x$ -- to "count" the squares modulo $m$ which are less than or equal to $x$:

  1. when $m$ is prime,
  2. when $m$ is a prime power,
  3. when $m$ is arbitrary, factorization given,
  4. when $m$ is arbitrary, no factorization given?

If $x_0 < x_1 < m$, then a set $S^m_{x_0,x_1}$ is equal to $S^m_{x_1} - S^m_{x_0-1}$, so the size of $S^m_{x_0,x_1}$ can be calculated from the sizes of $S^m_{x_1}$, $S^m_{x_0-1}$. Similarly, the number of squares modulo $m$ in any interval can be calculated.

share|improve this question
Probably O(m) is the simplest, just do $s_{n+1}= s_n + 2n+1$ mod m and test which $s_n$ fall into the desired interval. Even if you have a multiplicative basis for generating the quadratic residues, you still need to test the result to be less than $x$. If $x$ is small and if computing Jacobi symbols is cheap enough, you might try that alternative. Gerhard "Ask Me Not About Reciprocity" Paseman, 2012.11.13 –  Gerhard Paseman Nov 13 '12 at 20:43
You can even be smart about the O(m) algorithm, note that the first sqrt(x) residues are in the interval, and skip the next up to sqrt(m), etc. This might take the runtime down to O(m/x) or better. Gerhard "Ask Me About Simple Optimization" Paseman, 2012.11.13 –  Gerhard Paseman Nov 13 '12 at 20:47
Note that if $m\equiv3\pmod4$ is prime, then knowing $S_{(m-1)/2}^m$ is equivalent to knowing the class number of ${\bf Q}(\sqrt{-m})$. See, e.g., mathoverflow.net/questions/25707/… –  Gerry Myerson Nov 13 '12 at 22:45
add comment

1 Answer

To count them approximately, there is the Polya-Vinogradov et al estimate.

share|improve this answer
Another way to count them approximately is just to say, $x/2$. –  Gerry Myerson Nov 13 '12 at 22:39
It seems these problems are much more difficult than expected. (Not sure what to do with this in respect to the "mathoverflow-system") –  Stephan Wehner Nov 16 '12 at 4:17
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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