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$ Nov 13, 2012 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$ Nov 13, 2012 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$ Nov 13, 2012 at 22:45

1 Answer 1

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$ Nov 13, 2012 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$ Nov 16, 2012 at 4:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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