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 preprint of Paul Pollack contains several nice new results and valuable historic references regarding the above two questions. An even more recent preprint by him and Kübra Benli settles (1) in the sense that there are $\gg p^{1/9}$ prime quadratic residues $\ell<p$.