Finding the eigenvalue in Elkies' algorithm

One essential part of Elkies' algorithm for computing the group order of an elliptic curve defined over a finite field is the determination of the eig envalue of the Frobenius endomorphism. Here we compare from a practical poi nt of view several strategies for this search: the use of rational function s, the use of division polynomials, the babystep-giantstep method, and a ne w modification of this method that avoids the need for two fast exponentiat ions.