Fast algorithms for computing isogenies between elliptic curves

Alin Bostan (1) , Bruno Salvy (1) , Francois Morain (2, 3) , Eric Schost (2)

1 ALGO - Algorithms
2 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
3 TANC - Algorithmic number theory for cryptology

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.

Mots clés: Fast algorithms; elliptic curves; finite fields; isogenies; Schoof-Elkies-Atkin algorithm; Newton iteration

Domaines: Complexité [cs.CC]; Algorithme et structure de données [cs.DS]; Calcul formel [cs.SC]; Théorie des nombres [math.NT]

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