On the Distribution of Atkin and Elkies Primes
Given an elliptic curve \(E\) over a finite field \(\mathbb {F}_q\) of \(q\) elements, we say that an odd prime \(\ell \not \mid q\) is an Elkies prime for \(E\) if \(t_E^2 - 4q\) is a square modulo\(\ell \), where \(t_E = q+1 - \#E(\mathbb {F}_q)\) and \(\#E(\mathbb {F}_q)\) is the number of \(\mathbb {F}_q\)-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  0\) and a sufficiently large \(q\). We use this result to design and analyze a fast algorithm to generate random elliptic curves with \(\#E(\mathbb {F}_p)\) prime, where \(p\) varies uniformly over primes in a given interval \([x,2x]\).
elkies prime elliptic curve character sum 11g07 11l40 11y16