Skip to Main content Skip to Navigation

Fast Algorithms for Towers of Finite Fields and Isogenies

Luca de Feo 1, 2 
2 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
Abstract : In this thesis we apply techniques from computer algebra and language theory to speed up the elementary operations in some specific towers of finite fields. We apply our construction to the problem of computing isogenies between elliptic curves and obtain faster (both asymptotically and in practice) variants of Couveignes' algorithm. The document is divided in four parts. In Part I we recall some basic notions from algebra and complexity theory. Part II deals with the transposition principle: in it we generalize ideas of Bostan, Schost and Lecerf, and show that it is possible to automatically transpose computer programs without losses in time complexity and with a small loss in space complexity. Part III combines the results on the transposition principle with classical techniques from elimination theory; we apply these ideas to obtain asymptotically optimal algorithms for the arithmetic of Artin-Schreier towers of finite fields. We also describe an implementations of these algorithms. Finally, in Part IV we use the previous results to speed up Couveignes' algorithm and compare the result with the other state of the art algorithms for isogeny computation. We also present a new generalization of Couveignes' algorithm that computes isogenies of unknown degree.
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download
Contributor : Luca De Feo Connect in order to contact the contributor
Submitted on : Wednesday, March 30, 2011 - 12:47:56 AM
Last modification on : Friday, February 4, 2022 - 3:16:14 AM
Long-term archiving on: : Saturday, December 3, 2016 - 8:11:59 PM


  • HAL Id : tel-00547034, version 3



Luca de Feo. Fast Algorithms for Towers of Finite Fields and Isogenies. Mathematics [math]. Ecole Polytechnique X, 2010. English. ⟨tel-00547034v3⟩



Record views


Files downloads