Journal of the Ramanujan Mathematical Society

Mireille Fouquet ¹, Pierrick Gaudry ¹, Robert Harley ²

Affiliations
1 LIX, Ecole Poly Technique, 91128 Palaiseau Cedex, FR
2 ArgoTech, 26 Ter Rue Nicolai, 75012 Paris, FR

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 F_q with q = 2⁸⁰⁰⁹.

Full Text