Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



On the product of small Elkies primes

Author: Igor E. Shparlinski
Journal: Proc. Amer. Math. Soc. 143 (2015), 1441-1448
MSC (2010): Primary 11G07, 11L40, 11Y16, 14G50
Published electronically: December 1, 2014
MathSciNet review: 3314059
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Given an elliptic curve $ E$ over a finite field $ \mathbb{F}_q$ of $ q$ elements, we say that an odd prime $ \ell \nmid q$ is an Elkies prime for $ E$ if $ t_E^2 - 4q$ is a quadratic residue modulo $ \ell $, where $ t_E = q+1 - \char93 E(\mathbb{F}_q)$ and $ \char93 E(\mathbb{F}_q)$ is the number of $ \mathbb{F}_q$-rational points on $ E$. The Elkies primes are used in the presently most efficient algorithm to compute $ \char93 E(\mathbb{F}_q)$. In particular, the quantity $ L_q(E)$ defined as the smallest $ L$ such that the product of all Elkies primes for $ E$ up to $ L$ exceeds $ 4q^{1/2}$ is a crucial parameter of this algorithm. We show that there are infinitely many pairs $ (p, E)$ of primes $ p$ and curves $ E$ over $ \mathbb{F}_p$ with $ L_p(E) \ge c \log p \log \log \log p$ for some absolute constant $ c>0$, while a naive heuristic estimate suggests that $ L_p(E) \sim \log p$. This complements recent upper bounds on $ L_q(E)$ proposed by Galbraith and Satoh in 2002, conditional under the Generalised Riemann Hypothesis, and by Shparlinski and Sutherland in 2011, unconditional for almost all pairs $ (p,E)$.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 11G07, 11L40, 11Y16, 14G50

Retrieve articles in all journals with MSC (2010): 11G07, 11L40, 11Y16, 14G50

Additional Information

Igor E. Shparlinski
Affiliation: Department of Computing, Macquarie University, Sydney, NSW 2109, Australia
Address at time of publication: Department of Pure Mathematics, University of New South Wales, Sydney, NSW 2052, Australia

Keywords: Elliptic curves, Elkies primes, character sums
Received by editor(s): January 9, 2013
Received by editor(s) in revised form: August 27, 2013
Published electronically: December 1, 2014
Communicated by: Matthew A. Papanikolas
Article copyright: © Copyright 2014 American Mathematical Society

American Mathematical Society