Counting number of points on elliptic curves over F2m fields : An implementation study

Abstract

Hasse’s theorem states that:ifE {W g) Then |i| < 2y/q. This gives the bound on the number of points. In 1985, Schoof presented a polynomial time algorithm for computing The algorithm has running time of 0(log® q) bit operations. We discuss our efficient implementation of this algorithm over lF2m fields using the g F L Library, developed by Abhijit Das and C.E. Veni Madhavan. The implementation requires the computation of polynomial exponentiation and product modulo another polynomial of the order of 0(log^ q) . The degrees of the polynomials involved are very large. We have made the implementation efficient by optimizing the intermediate computations. We also study the structure of the group of points on the elliptic curves, for the fields up to F211 - We have written different routines for the elliptic curve point addition, multiplication etc. for this study. We have also implemented an ElGamal cryptosystem using the elliptic curve group over F2m fields