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 - http://www.scopus.com/inward/record.url?scp=84994246720&partnerID=8YFLogxK
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 -