For a prime (or prime power) $p$ and some absolute constant $C$ (say $C$ = 100), consider the set $A$ of all $1 \leq a \leq p/C$ such that $1 \leq a^2 \leq p/C$ modulo $p$. Is it known that $|A| = \Omega(p)$?



Distribution of quadratic residues in an interval
Yes. The points $(\frac{a}p,\frac{a^2\pmod p}p)$ are asymptotically equidistributed in $[0,1]^2$ by Weyl's criterion.


