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

Igor E. Shparlinski, Andrew V. Sutherland

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)

Abstract

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)4+o(1) expected time.

Original languageEnglish
Pages (from-to)308-322
Number of pages15
JournalLMS Journal of Computation and Mathematics
Volume18
Issue number1
DOIs
Publication statusPublished - 10 Apr 2015
Externally publishedYes

Fingerprint

Dive into the research topics of 'On the distribution of Atkin and Elkies primes for reductions of elliptic curves on average'. Together they form a unique fingerprint.

Cite this