Given a prime $p$ how many primes $\ellThere 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$.
 A: Let $\chi(n)$ denote the quadratic character modulo $p$ (so $\chi(n) = 1$ if $n$ is a quadratic residue modulo $p$, and $\chi(n)=-1$ if $n$ is a quadratic nonresidue modulo $p$). The difference between the number of primes that are quadratic residues and quadratic nonresidues is exactly $\sum_{\ell\lt p} \chi(\ell)$ where $\ell$ denotes a prime. One can deduce information about $\sum_{\ell\lt p} \chi(\ell)$ from information about $\sum_{\ell\lt p} \chi(\ell)\log\ell$, which in turn is almost the same as $\sum_{n\lt p} \chi(n)\Lambda(n)$ where $\Lambda$ is the von Mangoldt function. Such information is classically known, since the proof of the prime number theorem for arithmetic progressions hinges on it; it's important to note here that the summation goes up to $p$ itself rather than a general large $x$ as is typical for such statements. The answer then depends upon what zero-free region for the associated $L(s,\chi)$ you want to use or assume; if you get a bound that is $o(p)$, then the numbers of prime quadratic residues and prime quadratic nonresidues are very close to equal.
A: A comment to GH's elementary lower bound in question (1): Maybe there's a very minor error here. For example, if $p=7$ and $x=2$, then $x^2-p' = 11$ is not built up of primes enumerated in (1).  But this is easily resolved by restricting to odd values of $x$ in the case when $p\equiv3\pmod{4}$, and noting we then already know the prime factor $2$ of $x^2-p'$.
More substantial comment: Doesn't this construction give something a bit better than $\log p/\log\log p$? If $q_1, \dots, q_k$  are the primes enumerated in (1), then we get that $\gg\sqrt{p}$ numbers in $[1, 2p]$ are supported on primes from the list $2, q_1, \dots, q_k$. But the count of numbers in $[1,2p]$ supported on this set of primes is at most the count of numbers supported on the primes $2, 3, 5, \dots, p_{k+1}$, where $p_i$ denotes the $i$th prime in increasing order. In other words, it's at most $\Psi(2p, p_{k+1})$. It is known from the theory of smooth numbers that $\Psi(x, (\log x)^{A}) = x^{1-1/A +o(1)}$, as $x\to\infty$. So it looks like GH's argument gives that $k \geq (\log{p})^{2-o(1)}$, as $p\to\infty$. (Of course this is a little less elementary.)
A: GH from MO and Anonymous have commented above on (modest) lower bounds for the first problem.  Let me mention here that a version of problem 2 (of producing many non-residues) appeared in work of Bourgain and Lindenstrauss in connection with the QUE conjecture.  In particular, from Theorem 5.1 of their paper it follows that there is a positive constant $\delta$ such that at least $p^{\delta}$ of the primes $\ell$ below $p$ are quadratic non-residues $\pmod p$.  The proof is based on the fundamental lemma of sieve theory together with cancelation in character sums.  
Added:  To elaborate, Theorem 5.1 of Bourgain and Lindenstrauss's paper shows that if $N=p^{\beta}$ with $\beta \ge 1/4+\epsilon$ then there exists $\alpha>0$ such that ($\ell$ runs over primes below)
$$ 
\sum_{N^{\alpha} <\ell < N; (\frac{\ell}{p}) = -1} \frac{1}{\ell} \ge \frac 12 -\epsilon. 
$$ 
In particular the number of primes $\ell$ with $(\frac{\ell}{p}) =-1$ is trivially at least $(1/2-\epsilon)N^{\alpha}$.  Now use this with $N=p$, and we deduce the result mentioned above.  I didn't check the details, but I think one can get a pretty decent value of $\delta$ above -- maybe even as big as $3/8$ (the level of distribution is like $p^{\frac 34}$ and the sifting limit should be $1/2$).
