The Counting function for Elkies primes

Abstract

Let $E$ be an elliptic curve over a finite field ${\mathbb{F}}_q$ where $q$ is a prime power. The Schoof--Elkies--Atkin (SEA) algorithm is a standard method for counting the number of ${\mathbb{F}}_q$-points on $E$. The asymptotic complexity of the SEA algorithm depends on the distribution of the so-called Elkies primes. Assuming GRH, we prove that the least Elkies prime is bounded by $(2\log 4q+4{)}^2$ when $q\ge 10^9$. This is the first such explicit bound in the literature. Previously, Satoh and Galbraith established an upper bound of $O((\log q{)}^{2+\epsilon })$. Let $N_E(X)$ denote the number of Elkies primes less than $X$. Assuming GRH, we also show $$N_E(X)=\frac{\pi (X)}{2}+O\left(\frac{\sqrt{X}(\log qX{)}^2}{\log X}\right).$$