1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$ – Gerhard Paseman Nov 13 '12 at 20:43
  • $\begingroup$ 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 $\endgroup$ – Gerhard Paseman Nov 13 '12 at 20:47
  • 1
    $\begingroup$ 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/… $\endgroup$ – Gerry Myerson Nov 13 '12 at 22:45
1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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