On the product of small Elkies primes

Igor E. Shparlinski*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


Given an elliptic curve E over a finite field Fq of q elements, we say that an odd prime ℓ + q is an Elkies prime for E if t2 E − 4q is a quadratic residue modulo ℓ, where tE = q + 1 − #E(Fq) and #E(Fq) is the number of Fq-rational points on E. The Elkies primes are used in the presently most efficient algorithm to compute #E(Fq). In particular, the quantity Lq(E) defined as the smallest L such that the product of all Elkies primes for E up to L exceeds 4q1/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 Fp with Lp(E) ≥ c log p log log log p for some absolute constant c > 0, while a naive heuristic estimate suggests that Lp(E) ∼ log p. This complements recent upper bounds on Lq(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).

Original languageEnglish
Pages (from-to)1441-1448
Number of pages8
JournalProceedings of the American Mathematical Society
Issue number4
Publication statusPublished - 2015


  • Character sums
  • Elkies primes
  • Elliptic curves


Dive into the research topics of 'On the product of small Elkies primes'. Together they form a unique fingerprint.

Cite this