  We generalize Elkies's method, an essential ingredient in the SEA algorithm
to count points on elliptic curves over finite fields of large characteristic,
to the setting of p.p. abelian surfaces. Under reasonable assumptions related
to the distribution of Elkies primes, we obtain improvements over Schoof's
method in two cases. If the abelian surface A over Fq has RM by a fixed
quadratic field F, we reach the same asymptotic complexity Otilde(log4 q) as
the SEA algorithm up to constant factors depending on F. If A is defined over a
number field, we count points on A modulo sufficiently many primes in
Otilde(log6 q) binary operations on average. Numerical experiments demonstrate
the practical usability of our methods.
