# Counting modular squares in an interval

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.

-
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

Another way to count them approximately is just to say, $x/2$. –  Gerry Myerson Nov 13 '12 at 22:39