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], Polytechnique - X, CNRS - Centre National de la Recherche Scientifique : UMR7161, 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.
Document type :
Mathematics [math]. Ecole Polytechnique X, 2010. English
Contributor : Luca De Feo <>
Submitted on : Wednesday, March 30, 2011 - 12:47:56 AM
Last modification on : Thursday, January 5, 2017 - 1:21:18 AM
Document(s) archivé(s) le : 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


Document downloads