On the distribution of Atkin and Elkies primes for reductions of elliptic curves on average

Abstract

For an elliptic curve E/QE/Q without complex multiplication we study the distribution of Atkin and Elkies primes ℓℓ, on average, over all good reductions of EE modulo primes pp. We show that, under the generalized Riemann hypothesis, for almost all primes pp there are enough small Elkies primes ℓℓ to ensure that the Schoof–Elkies–Atkin point-counting algorithm runs in (logp)4+o(1)(log⁡p)4+o(1) expected time.