2014/03/31 by Igor E. Shparlinski, Andrew V. Sutherland
Computer Science · Mathematics · #Algebraic Geometry and Number Theory #Analytic Number Theory Research #Cardinality (data modeling) #Counting points on elliptic curves #Cryptography and Residue Arithmetic #Elliptic curve #Finite field #Integer (computer science) #Prime (order theory) #Rational number #Riemann hypothesis #Schoof's algorithm #math.NT #msc:11G07 #msc:11T06 #msc:11Y16
paper · pdf · doi:10.1142/s1793042117500099
published as Int. J. Number Theory 13 (2017), 133-152 · 21 pages, minor corrections, added a new section
arxiv created 2014/11/29 · openalex publication_date 2016/04/07 · openalex created_date 2016/06/24 · arxiv updated 2017/01/03 · openalex updated_date 2026/08/06
Assuming the Generalized Riemann Hypothesis, we design a deterministic algorithm that, given a prime [Formula: see text] and positive integer [Formula: see text], outputs an elliptic curve [Formula: see text] over the finite field [Formula: see text] for which the cardinality of [Formula: see text] is divisible by [Formula: see text]. The running time of the algorithm is [Formula: see text], and this leads to more efficient constructions of rational functions over [Formula: see text] whose image is small relative to [Formula: see text]. We also give an unconditional version of the algorithm that works for almost all primes [Formula: see text], and give a probabilistic algorithm with subexponential time complexity.