TY - JOUR
T1 - On the Distribution of Atkin and Elkies Primes
AU - Shparlinski, Igor E.
AU - Sutherland, Andrew V.
PY - 2014/4
Y1 - 2014/4
N2 - Given an elliptic curve E over a finite field Fq of q elements, we say that an odd prime ℓ {does not divide} q is an Elkies prime for E if tE2 - 4q is a square modulo ℓ, where (Formula presented.) is the number of Fq-rational points on E; otherwise, ℓ is called an Atkin prime. We show that there are asymptotically the same number of Atkin and Elkies primes ℓ < L on average over all curves E over Fq, provided that L ≥ (log q)ε for any fixed ε > 0 and a sufficiently large q. We use this result to design and analyze a fast algorithm to generate random elliptic curves with #E(Fp) prime, where p varies uniformly over primes in a given interval [x, 2x].
AB - Given an elliptic curve E over a finite field Fq of q elements, we say that an odd prime ℓ {does not divide} q is an Elkies prime for E if tE2 - 4q is a square modulo ℓ, where (Formula presented.) is the number of Fq-rational points on E; otherwise, ℓ is called an Atkin prime. We show that there are asymptotically the same number of Atkin and Elkies primes ℓ < L on average over all curves E over Fq, provided that L ≥ (log q)ε for any fixed ε > 0 and a sufficiently large q. We use this result to design and analyze a fast algorithm to generate random elliptic curves with #E(Fp) prime, where p varies uniformly over primes in a given interval [x, 2x].
KW - Character sum
KW - Elkies prime
KW - Elliptic curve
UR - http://www.scopus.com/inward/record.url?scp=84896401336&partnerID=8YFLogxK
UR - http://purl.org/au-research/grants/arc/DP130100237
U2 - 10.1007/s10208-013-9181-9
DO - 10.1007/s10208-013-9181-9
M3 - Article
AN - SCOPUS:84896401336
SN - 1615-3375
VL - 14
SP - 285
EP - 297
JO - Foundations of Computational Mathematics
JF - Foundations of Computational Mathematics
IS - 2
ER -