  Given an elliptic curve $E$ over a finite field $\F_q$ of $q$ elements, we
say that an odd prime $\ell \nmid q$ is an Elkies prime for $E$ if $t_E^2 - 4q$
is a quadratic residue modulo $\ell$, where $t_E = q+1 - #E(\F_q)$ and
$#E(\F_q)$ is the number of $\F_q$-rational points on $E$. These primes are
used in the presently most efficient algorithm to compute $#E(\F_q)$. In
particular, the bound $L_q(E)$ such that the product of all Elkies primes for
$E$ up to $L_q(E)$ exceeds $4q^{1/2}$ is a crucial parameter of this algorithm.
We show that there are infinitely many pairs $(p, E)$ of primes $p$ and curves
$E$ over $\F_p$ with $L_p(E) \ge c \log p \log \log \log p$ for some absolute
constant $c>0$, while a naive heuristic estimate suggests that $L_p(E) \sim
\log p$. This complements recent results of Galbraith and Satoh (2002),
conditional under the Generalised Riemann Hypothesis, and of Shparlinski and
Sutherland (2012), unconditional for almost all pairs $(p,E)$.
