Counting the number of points on elliptic curves over finite fields of characteristic greater than three.(English)Zbl 0839.11026

Adleman, Leonard M. (ed.) et al., Algorithmic number theory. 1st international symposium, ANTS-I, Ithaca, NY, USA, May 6-9, 1994. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 877, 60-70 (1994).
The authors describe an implementation of an algorithm to count points on elliptic curves modulo $$p$$. They have incorporated important practical improvements by A. O. L. Atkin and N. D. Elkies to the original algorithm. As an illustration the authors counted the number of points on an elliptic curve modulo a 375 digit prime number.
The title of the paper is somewhat misleading: the algorithm implemented by the authors does not work for large finite fields of small characteristic. The problems that arise in these cases have only recently been solved by J.-M. Couveignes in his thesis [Quelques calculs en théorie des nombres, Thèse Bordeaux I, july 1994].
For the entire collection see [Zbl 0802.00018].
Reviewer: R.Schoof (Roma)

MSC:

 11G20 Curves over finite and local fields 11Y16 Number-theoretic algorithms; complexity 14H52 Elliptic curves 14Q05 Computational aspects of algebraic curves