On the Distribution of Atkin and Elkies Primes

Igor E. Shparlinski, Andrew V. Sutherland

Research output: Contribution to journalArticle

5 Citations (Scopus)

Abstract

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].

Original languageEnglish
Pages (from-to)285-297
Number of pages13
JournalFoundations of Computational Mathematics
Volume14
Issue number2
DOIs
Publication statusPublished - Apr 2014
Externally publishedYes

Keywords

  • Character sum
  • Elkies prime
  • Elliptic curve

Fingerprint Dive into the research topics of 'On the Distribution of Atkin and Elkies Primes'. Together they form a unique fingerprint.

Cite this