There was this question for which my response was unusally popular, so I dare to ask the following:

(1) Given a prime $p>2$, how many primes $\ell < p$ there exist which are quadratic residues mod $p$?

(2) Given a prime $p>2$, how many primes $\ell < p$ there exist which are quadratic nonresidues mod $p$?

As for (1) I can prove $\gg\log p/\log\log p$ by an elementary argument. Indeed, put $p':=(-1)^{(p-1)/2}p$ and observe, by quadratic reciprocity, that a prime $\ell\neq p$ divides some value $x^2-p'$ for $x\in\mathbb{Z}$ if and only if $\ell$ is a quadratic residue mod $p$. Now consider $|x^2-p'|$ for $0 < x < \sqrt{p}$: these are integers in $(0,p)$ or $(p,2p)$ depending on $p$ mod $4$. At any rate, these numbers are built up from the $k$ primes enumerated under (1), and their number is $\gg\sqrt{p}$. As each of the $k$ prime exponents is $\ll\log p$, we conclude $\sqrt{p}\ll(\log p)^k$ and my claim follows.

**Added 1.** As Anonymous pointed out, we should restrict to odd $0 < x < \sqrt{p}$, and talk about the odd part of $|x^2-p'|$. In addition, using the upper bound part of (7.16) on p. 203 of Montgomery-Vaughan: Multiplicative Number Theory (proof on pp. 204-208), we can see $k>(\log p)^{2-o(1)}$ for the number of primes under (1).

**Added 2.** Regarding (2), Lucia pointed out that $\gg p^\delta$ follows with a decent $\delta>0$ from a result of Bourgain and Lindenstrauss. I found this response very satisfactory, and I accepted it officially. Still, I would welcome any further developments regarding the above questions (1) and (2).

**Added 3.** The recent arXiv preprint of Paul Pollack contains several nice new results and valuable historic references regarding the above two questions.