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
DOI: https://doi.org/10.1090/S0002-9939-2014-12345-8
Published electronically: December 1, 2014
MathSciNet review: 3314059
Full-text PDF Free Access

Abstract | 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 - \#E(\mathbb {F}_q)$ and $\#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 $\#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)$.


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
MR Author ID: 192194
Email: igor.shparlinski@mq.edu.au, igor.shparlinski@unsw.edu.au

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