Schoof’s algorithm computes the number m m of points on an elliptic curve E E defined over a finite field F q {\Bbb F}_q . Schoof determines m m modulo small primes ℓ \ell using the characteristic equation of the Frobenius of E E and polynomials of degree O ( ℓ 2 ) 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 ( ℓ ) 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 x -values only.