Abstract : We describe a fast algorithm for counting points on elliptic curves defined over finite fields of small characteristic, following Satoh. Our main contribution is an extension to characteristics two and three. We give a detailed description with the optimisations necessary for an efficient implementation. Finally we give the number of points we have computed on a ``random'' curve defined over the field Fq with q=2^8009.
https://hal.inria.fr/inria-00512791 Contributor : Pierrick GaudryConnect in order to contact the contributor Submitted on : Tuesday, August 31, 2010 - 3:56:56 PM Last modification on : Thursday, February 3, 2022 - 11:14:41 AM Long-term archiving on: : Wednesday, December 1, 2010 - 2:52:34 AM
Mireille Fouquet, Pierrick Gaudry, Robert Harley. An extension of Satoh's algorithm and its implementation. Journal of the Ramanujan Mathematical Society, Ramanujan Mathematical Society, 2000, 15, pp.281-318. ⟨inria-00512791⟩