Counting points on elliptic curves over finite fields (Q1909875)

The author reports on algorithms for counting the number of points on an elliptic curve over a finite field. The first one works well when the finite field is not too large and is based on Shank's baby-step-giant-step strategy [\textit{D. Shanks}, 1969 Number Theory Institute, Proc. Symp. Pure Math. 20, 415-440 (1971; Zbl 0223.12006)]. Then he discusses an improvement due to Mestre which avoids some group theoretical problems in this algorithm; this has been implemented in the computer algebra package PARI [\textit{H. Cohen}, A course in computational number theory, Grad. Texts Math. 138 (1993; Zbl 0786.11071), Alg. 7.4.12; \textit{C. Batut}, \textit{D. Bernardini}, \textit{H. Cohen} and \textit{M. Olivier}, User's guide to PARI-GP, version 1.30, Bordeaux (1990)]. The second algorithm is efficient when the endomorphism ring of the elliptic curve is known, and it is based on a reduction algorithm for lattices in \(\mathbb{R}^2\). A related algorithm due to Cornacchia and Lenstra's proof of its correctness are also discussed. Finally the last algorithm is a deterministic one which runs in polynomial time and is based on calculations with torsion points. Practical improvements due to Atkin and Elkies are also presented. The latter methods can be extended to large finite fields of small characteristics, and its origin comes from cryptography [\textit{A. J. Menezes}, \textit{S. A. Vanstone} and \textit{R. J. Zuccherato}, Math. Comput. 60, 407-420 (1993; Zbl 0809.14045)].