Computing isogenies in \(\mathbb{F}_{2^n}\). (English) Zbl 0911.11029

Lercier, Reynald

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

Keywords:

elliptic curve over a finite field; computation of isogenies; algorithm; complexity