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

Igor E. Shparlinski; Andrew V. Sutherland

doi:10.1112/S1461157015000017

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 journal › Article › peer-review

13 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 language	English
Pages (from-to)	308-322
Number of pages	15
Journal	LMS Journal of Computation and Mathematics
Volume	18
Issue number	1
DOIs	https://doi.org/10.1112/S1461157015000017
Publication status	Published - 10 Apr 2015
Externally published	Yes

Access to Document

10.1112/S1461157015000017

Cite this

@article{89b99025cc834fa1b4639b822cd265ea,

title = "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 ℓ, 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.",

author = "Shparlinski, \{Igor E.\} and Sutherland, \{Andrew V.\}",

year = "2015",

month = apr,

day = "10",

doi = "10.1112/S1461157015000017",

language = "English",

volume = "18",

pages = "308--322",

journal = "LMS Journal of Computation and Mathematics",

issn = "1461-1570",

publisher = "London Mathematical Society",

number = "1",

}

TY - JOUR

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

AU - Shparlinski, Igor E.

AU - Sutherland, Andrew V.

PY - 2015/4/10

Y1 - 2015/4/10

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

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

UR - https://www.scopus.com/pages/publications/84994246720

U2 - 10.1112/S1461157015000017

DO - 10.1112/S1461157015000017

M3 - Article

AN - SCOPUS:84994246720

SN - 1461-1570

VL - 18

SP - 308

EP - 322

JO - LMS Journal of Computation and Mathematics

JF - LMS Journal of Computation and Mathematics

IS - 1

ER -

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

Abstract

Access to Document

Other files and links

Fingerprint

Cite this