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

For an elliptic curve E/Q without complex multiplication we study the distribution of Atkin and Elkies primes , 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 to ensure that the Schoof–Elkies–Atkin point-counting algorithm runs in (log p)⁴⁺ᵒ⁽¹⁾ expected time.