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

Abstract

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 Generalised 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.

20 pages, to appear in LMS J. Comput. Math

References in corpus (3)

• Computing Hasse-Witt matrices of hyperelliptic curves in average polynomial time
• Computing Hasse-Witt matrices of hyperelliptic curves in average polynomial time, II
• Even faster integer multiplication

Cited by in corpus (8)

• Computing images of Galois representations attached to elliptic curves
• $\ell$-adic images of Galois for elliptic curves over $\mathbb{Q}$
• Sato-Tate groups of y^2=x^8+c and y^2=x^7-cx
• Computing the endomorphism ring of an elliptic curve over a number field
• Computing cardinalities of Q-curve reductions over finite fields
• Computing Euler factors of genus 2 curves at odd primes of almost good reduction
• Doubly isogenous curves of genus two with a rational action of $D_6$
• From the Birch and Swinnerton-Dyer conjecture to Nagao's conjecture