Computing isogenies in $GF(2^n)$

Reynald Lercier (1)

1 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]

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 $GF(2^n)$ is the computation of isogenies of prime degree $\ell$. The best method so far is due to Couveignes and needs asymptotically $O(\ell^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.

Domaines: Théorie des nombres [math.NT]; Géométrie algébrique [math.AG]

Reynald Lercier. Computing isogenies in $GF(2^n)$. ANTS-II, May 1996, Talence, France. ⟨10.1007/3-540-61581-4_55⟩. ⟨hal-01102045⟩