Fast Algorithms for Towers of Finite Fields and Isogenies

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 :
Theses
Mathematics. Ecole Polytechnique X, 2010. English


https://pastel.archives-ouvertes.fr/tel-00547034
Contributor : Luca De Feo <>
Submitted on : Wednesday, March 30, 2011 - 12:47:56 AM
Last modification on : Friday, March 27, 2015 - 4:02:23 PM

Identifiers

  • HAL Id : tel-00547034, version 3

Collections

Citation

Luca De Feo. Fast Algorithms for Towers of Finite Fields and Isogenies. Mathematics. Ecole Polytechnique X, 2010. English. <tel-00547034v3>

Export

Share

Metrics

Consultation de
la notice

335

Téléchargement du document

171