Let E/Q be an elliptic curve with complex multiplication. We study the average size of τ(#E(Fp)) as p varies over primes of good ordinary reduction. We work out in detail the case of E: y2 = x3 − x, where we prove that
$$\begin{equation}
\sum_{\substack{p \leq x \\p \equiv 1\pmod{4}}} \tau(\#E({\bf{F}}_p)) \sim \left(\frac{5\pi}{16} \prod_{p > 2} \frac{p^4-\chi(p)}{p^2(p^2-1)}\right)x, \quad\text{as $x\to\infty$}.
\end{equation}$$
Here χ is the nontrivial Dirichlet character modulo 4. The proof uses number field analogues of the Brun–Titchmarsh and Bombieri–Vinogradov theorems, along with a theorem of Wirsing on mean values of nonnegative multiplicative functions.
Now suppose that E/Q is a non-CM elliptic curve. We conjecture that the sum of τ(#E(Fp)), taken over p ⩽ x of good reduction, is ~cEx for some cE > 0, and we give a heuristic argument suggesting the precise value of cE. Assuming the Generalized Riemann Hypothesis for Dedekind zeta functions, we prove that this sum is ≍Ex. The proof uses combinatorial ideas of Erdős.