2011/12/19 by Igor E. Shparlinski, Andrew V. Sutherland · 1 citation
Computer Science · Mathematics · #Algebraic number field #Analytic Number Theory Research #Coding theory and cryptography #Cryptography and Residue Arithmetic #Distribution (mathematics) #Elliptic curve #Field (mathematics) #Finite field #Interval (graph theory) #Modulo #Prime (order theory) #Square (algebra) #math.NT #msc:11G07 #msc:11Y16 #msc:14H52 #msc:68Q25
paper · pdf · doi:10.1007/s10208-013-9181-9
published as Foundations of Computational Mathematics 14 (2014), 285-297 · 17 pages, minor edits
arxiv created 2011/12/19 · openalex publication_date 2014/02/18 · arxiv updated 2014/06/20 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05
Given an elliptic curve E over a finite field Fq of q elements, we say that an odd prime ell not dividing q is an Elkies prime for E if tE2 - 4q is a square modulo ell, where tE = q+1 - #E(Fq) and #E(Fq) is the number of Fq-rational points on E; otherwise ell is called an Atkin prime. We show that there are asymptotically the same number of Atkin and Elkies primes ell < L on average over all curves E over Fq, provided that L >= (log q)e for any fixed e > 0 and a sufficiently large q. We use this result to design and analyse a fast algorithm to generate random elliptic curves with #E(Fp) prime, where p varies uniformly over primes in a given interval [x,2x].