# zbMATH — the first resource for mathematics

Computing isogenies in $$\mathbb{F}_{2^n}$$. (English) Zbl 0911.11029
Cohen, Henri (ed.), Algorithmic number theory. Second international symposium, ANTS-II, Talence, France, May 18-23, 1996. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1122, 197-212 (1996).
Summary: 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 $$\mathbb{F}_{2^n}$$ is the computation of isogenies of prime degree $$\ell$$ [R. Schoof, J. Theor. Nombres Bordx. 7, 219-254 (1993; Zbl 0852.11073)]. The best method so far is due to J.-M. Couveignes [Quelques calculs en théorie des nombres, Thèse, Univ. Bordeaux (1994)] and needs asymptotically $$O(\ell^3)$$ field operations. The author outlines some nice properties satisfied by these isogenies and shows how to get from them a new algorithm that performs better in practice than Couveignes’s though of the same complexity. On a representative problem, he gains a speed-up of 5 for the whole computation.
For the entire collection see [Zbl 0852.00023].

##### MSC:
 11G20 Curves over finite and local fields 11Y16 Number-theoretic algorithms; complexity