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)

Request Permissions   Purchase Content 


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?)

  • [1] R. Avanzi, H. Cohen, C. Doche, G. Frey, T. Lange, K. Nguyen and F. Vercauteren, Elliptic and hyperelliptic curve cryptography: Theory and practice, CRC Press, 2005.
  • [2] Stephan Baier and Liangyi Zhao, On primes in quadratric progressions, Int. J. Number Theory 5 (2009), no. 6, 1017-1035. MR 2569742 (2010k:11147),
  • [3] Mei-Chu Chang, Short character sums for composite moduli, J. Anal. Math. 123 (2014), 1-33. MR 3233573,
  • [4] Max Deuring, Die Typen der Multiplikatorenringe elliptischer Funktionenkörper, Abh. Math. Sem. Hansischen Univ. 14 (1941), 197-272 (German). MR 0005125 (3,104f)
  • [5] Noam D. Elkies, Elliptic and modular curves over finite fields and related computational issues, Computational perspectives on number theory (Chicago, IL, 1995) AMS/IP Stud. Adv. Math., vol. 7, Amer. Math. Soc., Providence, RI, 1998, pp. 21-76. MR 1486831 (99a:11078)
  • [6] Henryk Iwaniec and Emmanuel Kowalski, Analytic number theory, American Mathematical Society Colloquium Publications, vol. 53, American Mathematical Society, Providence, RI, 2004. MR 2061214 (2005h:11005)
  • [7] Guang Shi Lü and Hai Wei Sun, Prime in quadratic progressions on average, Acta Math. Sin. (Engl. Ser.) 27 (2011), no. 6, 1187-1194. MR 2795366 (2012j:11182),
  • [8] Florian Luca and Igor E. Shparlinski, On quadratic fields generated by polynomials, Arch. Math. (Basel) 91 (2008), no. 5, 399-408. MR 2461203 (2010c:11119),
  • [9] Hugh L. Montgomery and Robert C. Vaughan, Multiplicative number theory. I. Classical theory, Cambridge Studies in Advanced Mathematics, vol. 97, Cambridge University Press, Cambridge, 2007. MR 2378655 (2009b:11001)
  • [10] Takakazu Satoh, On $ p$-adic point counting algorithms for elliptic curves over finite fields, Algorithmic number theory (Sydney, 2002) Lecture Notes in Comput. Sci., vol. 2369, Springer, Berlin, 2002, pp. 43-66. MR 2041073 (2004k:11098),
  • [11] René Schoof, Elliptic curves over finite fields and the computation of square roots mod $ p$, Math. Comp. 44 (1985), no. 170, 483-494. MR 777280 (86e:11122),
  • [12] Igor E. Shparlinski and Andrew V. Sutherland, On the distribution of Atkin and Elkies primes, Found. Comput. Math. 14 (2014), no. 2, 285-297. MR 3179585,
  • [13] Joseph H. Silverman, The arithmetic of elliptic curves, 2nd ed., Graduate Texts in Mathematics, vol. 106, Springer, Dordrecht, 2009. MR 2514094 (2010i:11005)

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