On the product of small Elkies primes

Abstract:

Given an elliptic curve $E$ over a finite field $\mathbb {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(\mathbb {F}_q)$ and $\#E(\mathbb {F}_q)$ is the number of $\mathbb {F}_q$-rational points on $E$. The Elkies primes are used in the presently most efficient algorithm to compute $\#E(\mathbb {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 $\mathbb {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 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)$.