Fast algorithms for computing isogenies between elliptic curves

Alin Bostan 1 Bruno Salvy 1 Francois Morain 2, 3 Eric Schost 2
1 ALGO - Algorithms
Inria Paris-Rocquencourt
3 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
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.
Complete list of metadatas

Cited literature [52 references]  Display  Hide  Download

https://hal.inria.fr/inria-00091441
Contributor : Alin Bostan <>
Submitted on : Wednesday, September 6, 2006 - 1:35:05 PM
Last modification on : Wednesday, March 27, 2019 - 4:41:29 PM
Long-term archiving on : Tuesday, April 6, 2010 - 12:47:51 AM

Identifiers

Collections

Citation

Alin Bostan, Bruno Salvy, Francois Morain, Eric Schost. Fast algorithms for computing isogenies between elliptic curves. [Research Report] 2006, pp.28. ⟨inria-00091441⟩

Share

Metrics

Record views

855

Files downloads

316