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

Igor E. Shparlinski, Andrew V. Sutherland

Published 2014-04-01, updated 2014-11-29Version 2

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