Journal of the Ramanujan Mathematical Society

Open Access Open Access  Restricted Access Subscription Access
Open Access Open Access Open Access  Restricted Access Restricted Access Subscription Access

An Extension of Satoh's Algorithm and Its Implementation


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

   Subscribe/Renew Journal


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 = 28009.
User
Subscription Login to verify subscription
Notifications
Font Size

Abstract Views: 146

PDF Views: 0




  • An Extension of Satoh's Algorithm and Its Implementation

Abstract Views: 146  |  PDF Views: 0

Authors

Mireille Fouquet
LIX, Ecole Poly Technique, 91128 Palaiseau Cedex, France
Pierrick Gaudry
LIX, Ecole Poly Technique, 91128 Palaiseau Cedex, France
Robert Harley
ArgoTech, 26 Ter Rue Nicolai, 75012 Paris, France

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 = 28009.