Reynald Lercier

R. Lercier. Computing isogenies in GF(2ⁿ). In H. Cohen, editor, Algorithmic Number Theory: Second International Symposium, ANTS-II Talence, France, May 18-23, 1996 Proceedings, volume 1122 of Lecture Notes in Computer Science, pages 197-212. Springer Berlin / Heidelberg, May 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 GF(2ⁿ) is the computation of isogenies of prime degree l. The best method so far is due to Couveignes and needs asymptotically O(l³) 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

[ bib | preprint | publication ] Back