Finding elliptic curves with a subgroup of prescribed size

Igor E. Shparlinski*, Andrew V. Sutherland

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


Assuming the Generalized Riemann Hypothesis, we design a deterministic algorithm that, given a prime p and positive integer m = o(p1/2(logp)-4), outputs an elliptic curve E over the finite field p for which the cardinality of E(p) is divisible by m. The running time of the algorithm is mp1/2+o(1), and this leads to more efficient constructions of rational functions over p whose image is small relative to p. We also give an unconditional version of the algorithm that works for almost all primes p, and give a probabilistic algorithm with subexponential time complexity.

Original languageEnglish
Pages (from-to)133-152
Number of pages20
JournalInternational Journal of Number Theory
Issue number1
Publication statusPublished - 1 Feb 2017
Externally publishedYes


  • divisibility
  • Elliptic curve
  • prime quadratic residues
  • smooth numbers


Dive into the research topics of 'Finding elliptic curves with a subgroup of prescribed size'. Together they form a unique fingerprint.

Cite this