On the distribution of Atkin and Elkies primes (Q404278)

Let \(\mathbb F_q\) be a finite field of \(q\) elements and characteristic \(p\). For an elliptic curve \(E\) over \(\mathbb F_q\), let \(\#E(\mathbb F_q)\) denote the number of \(\mathbb F_q\)-rational points on \(E\) and set \(t_E=q-1-\#E(\mathbb F_q)\). An odd prime \(\ell\neq p\) is an \textit{Elkies prime} for \(E\) if \(t_E^2-4q\) is a quadratic residue modulo \(\ell\) and an \textit{Atkin prime} otherwise. Define \(N_a(E,L)\) and \(N_e(E,L)\) as, respectively, the number of Atkin and Elkies primes \(\ell\) in the interval \([L, 2L]\) for the elliptic curve \(E\). The authors show that \(N_a(E,L)\) and \(N_e(E,L)\) are asymptotically equal on average over all curves \(E\) over \(\mathbb F_q\), provided \(L\geq (\log q)^{\varepsilon}\), for any \(\varepsilon>0\) and sufficiently large \(q\). This does not depend on the generalized Riemann hypothesis (GRH) and includes smaller \(L\) than previous results that do require the GRH. This result is used to design and analyze a fast algorithm to generate random elliptic curves with \(\#E(\mathbb F_q)\) a prime. Such curves \(E\) arise in cryptographic applications. See also the author and \textit{A. V. Sutherland} [``On the distribution of Atkin and Elkies primes for reductions of elliptic curves on average.'' LMS J. Comput. Math. 18, 308--322 (2015; Zbl 1400.11164)].