Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

Fast algorithms for computing isogenies between elliptic curves


Authors: A. Bostan, F. Morain, B. Salvy and É. Schost
Journal: Math. Comp. 77 (2008), 1755-1778
MSC (2000): Primary 11Y16, 94A60; Secondary 11G20
Published electronically: January 18, 2008
MathSciNet review: 2398793
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We survey algorithms for computing isogenies between elliptic curves defined over a field of characteristic either 0 or a large prime. We introduce a new algorithm that computes an isogeny of degree $ \ell$ ($ \ell$ different from the characteristic) in time quasi-linear with respect to $ \ell$. This is based in particular on fast algorithms for power series expansion of the Weierstrass $ \wp$-function and related functions.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y16, 94A60, 11G20

Retrieve articles in all journals with MSC (2000): 11Y16, 94A60, 11G20


Additional Information

A. Bostan
Affiliation: Algorithms Project, INRIA Rocquencourt, 78153 Le Chesnay, France
Email: Alin.Bostan@inria.fr

F. Morain
Affiliation: Projet TANC, Pôle Commun de Recherche en Informatique du Plateau de Saclay, CNRS, École polytechnique, INRIA, Université Paris-Sud. The author is on leave from the French Department of Defense, Délégation Générale pour l’Armement.
Email: morain@lix.polytechnique.fr

B. Salvy
Affiliation: Algorithms Project, INRIA Rocquencourt, 78153 Le Chesnay, France
Email: Bruno.Salvy@inria.fr

É. Schost
Affiliation: Department of Computer Science, Room 415, Middlesex College, University of Western Ontario, London, Ontario, N6A 5B7, Canada
Email: eschost@uwo.ca

DOI: http://dx.doi.org/10.1090/S0025-5718-08-02066-8
PII: S 0025-5718(08)02066-8
Keywords: Fast algorithms, elliptic curves, finite fields, isogenies, Schoof-Elkies-Atkin algorithm, Newton iteration
Received by editor(s): September 5, 2006
Received by editor(s) in revised form: April 3, 2007
Published electronically: January 18, 2008
Article copyright: © Copyright 2008 American Mathematical Society