Fast algorithms for computing isogenies between elliptic curves

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.

Cited by in corpus (22)

• The Beta Ansatz: A Tale of Two Complex Structures
• A Subexponential Algorithm for Evaluating Large Degree Isogenies
• Fast algorithms for computing isogenies between ordinary elliptic curves in small characteristic
• On the evaluation of modular polynomials
• Computing separable isogenies in quasi-optimal time
• On p-adic differential equations with separation of variables
• Explicit isogenies in quadratic time in any characteristic
• On the Distribution of Atkin and Elkies Primes
• Finding Orientations of Supersingular Elliptic Curves and Quaternion Orders
• Isogenies of Elliptic Curves: A Computational Approach
• Dual Elliptic Primes and Applications to Cyclotomy Primality Proving
• On the computation of coefficients of modular forms: the reduction modulo p approach
• On Elkies subgroups of l-torsion points in elliptic curves defined over a finite field
• Explicit classification of isogeny graphs of rational elliptic curves
• Computing isogenies from modular equations in genus two
• A faster pseudo-primality test
• Computing cardinalities of Q-curve reductions over finite fields
• Orienting supersingular isogeny graphs
• Evaluating modular equations for abelian surfaces
• Accelerating the Couveignes Rostovtsev Stolbunov key exchange protocol
• Computing isogenies between Jacobian of curves of genus 2 and 3
• On elliptic curves with an isogeny of degree 7