Remarks on the Schoof-Elkies-Atkin algorithm

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.