On the distribution of Atkin and Elkies primes for reductions of elliptic curves on average
Igor E. Shparlinski, Andrew V. Sutherland · LMS Journal of Computation and Mathematics · 2015
For an elliptic curve $E/\mathbb{Q}$ without complex multiplication we study the distribution of Atkin and Elkies primes $\ell$ , 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 $\ell$ to ensure that the Schoof–Elkies–Atkin point-counting algorithm runs in $(\log p)^{4+o(1)}$ expected time.