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$:

- when $m$ is prime,
- when $m$ is a prime power,
- when $m$ is arbitrary, factorization given,
- 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.