Remarks on the Schoof-Elkies-Atkin algorithm

Abstract:

Schoof’s algorithm computes the number $m$ of points on an elliptic curve $E$ defined over a finite field ${\Bbb F}_q$. Schoof determines $m$ modulo small primes $\ell$ using the characteristic equation of the Frobenius of $E$ and polynomials of degree $O(\ell ^2)$. With the works of Elkies and Atkin, we have just to compute, when $\ell$ is a “good" prime, an eigenvalue of the Frobenius using polynomials of degree $O(\ell )$. In this article, we compute the complexity of Müller’s algorithm, which is the best known method for determining one eigenvalue and we improve the final step in some cases. Finally, when $\ell$ is “bad", we describe how to have polynomials of small degree and how to perform computations, in Schoof’s algorithm, on $x$-values only.