Computing isogenies in F 2 n
Reynald Lercier · 1996
. Contrary to what happens over prime fields of large characteristic, the main cost when counting the number of points of an elliptic curve E over F2 n is the computation of isogenies of prime degree `. The best method so far is due to Couveignes and needs asymptotically O(` 3 ) field operations. We outline in this article some nice properties satisfied by these isogenies and show how we can get from them a new algorithm that seems to perform better in practice than Couveignes's though of the same complexity. On a representative problem, we gain a speed-up of 5 for the whole computation. 1 Introduction Many number theoretic algorithms are based on elliptic curves, among which integer factorization [5] or primality testing [1]. More directly, counting the number of points on these curves is essential to design secure cryptographical public schemes [8]. Algorithms to compute the cardinality of elliptic curves defined over finite fields of large characteristic give now satisfying resul...