Deciding if $m \not \in \{x^2 \bmod p : x \in \mathbb N\}$, also cardinality

Question

Let $S_p = \{x^2 \bmod p : x\in\mathbb N\}$, with $p$ prime.

Is there an efficient way to determine if an arbitrary $m \not \in S_p$, where $m \in\mathbb N \bmod p$, without generating $S_p$?

E.g. $S_5 = \{0, 1, 4\}$, $m \in \{2, 3\}$.

Also is there a way to estimate $|S_p|$?

$\mathbb{N}^2$ stands for the cartesian product, not for the squares of the natural numbers. — Aravind, Sep 21 '15 at 18:31
Can someone review the edit suggested by an anonymous user? I don't seem to have the privileges to accept or reject it. — Yimin Rong, Sep 21 '15 at 19:01

score 1 · Accepted Answer · answered Sep 21 '15 at 18:36

1

To check if a number is a square or non-square mod $p$, you can use Euler's criterion: compute $a^{\frac{p-1}{2}}$ (mod p) and check if it is equal to 1 or -1.

The number of squares is $(p+1)/2$ as the earlier answer shows.

answered Sep 21 '15 at 18:36

Aravind

6,150

Is a the number we're checking? – Yimin Rong Sep 21 '15 at 18:52
Yes, $a$ is the number we're checking. – Aravind Sep 21 '15 at 18:57
Thank you. Of note is that aⁿ is easily optimized to O(log₂(n)) modular multiplications. – Yimin Rong Sep 22 '15 at 17:52

Deciding if $m \not \in \{x^2 \bmod p : x \in \mathbb N\}$, also cardinality

1 Answers1