An extension of Satoh's algorithm and its implementation

Mireille Fouquet (1) , Pierrick Gaudry (1) , Robert Harley (2)

1 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
2 CRISTAL - Typed programming, modularity and compilation

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.

Domaines: Cryptographie et sécurité [cs.CR]

Mireille Fouquet, Pierrick Gaudry, Robert Harley. An extension of Satoh's algorithm and its implementation. Journal of the Ramanujan Mathematical Society, 2000, 15, pp.281-318. ⟨inria-00512791⟩