On the product of small Elkies primes

Given an elliptic curve E over a finite field F_q of q elements, we say that an odd prime ℓ + q is an Elkies prime for E if t² _E − 4q is a quadratic residue modulo ℓ, where t_E = q + 1 − #E(F_q) and #E(F_q) is the number of F_q-rational points on E. The Elkies primes are used in the presently most efficient algorithm to compute #E(F_q). In particular, the quantity L_q(E) defined as the smallest L such that the product of all Elkies primes for E up to L 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) ≥ c log p log log log p for some absolute constant c > 0, while a naive heuristic estimate suggests that L_p(E) ∼ log p. This complements recent upper bounds on L_q(E) proposed by Galbraith and Satoh in 2002, conditional under the Generalised Riemann Hypothesis, and by Shparlinski and Sutherland in 2011, unconditional for almost all pairs (p,E).