  Let $E$ be an elliptic curve over a finite field $\mathbb{F}_q$ where $q$ is
a prime power. The Schoof--Elkies--Atkin (SEA) algorithm is a standard method
for counting the number of $\mathbb{F}_q$-points on $E$. The asymptotic
complexity of the SEA algorithm depends on the distribution of the so-called
Elkies primes.
  Assuming GRH, we prove that the least Elkies prime is bounded by $(2\log
4q+4)^2$ when $q\geq 10^9$. This is the first such explicit bound in the
literature. Previously, Satoh and Galbraith established an upper bound of
$O((\log q)^{2+\varepsilon})$.
  Let $N_E(X)$ denote the number of Elkies primes less than $X$. Assuming GRH,
we also show $$
  N_E(X)=\frac{\pi(X)}{2}+O\left(\frac{\sqrt{X}(\log qX)^2}{\log X}\right)\,.
$$
