Fast algorithms for computing isogenies between elliptic curves

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 b...

Full description

Saved in:
Bibliographic Details
Published in:Mathematics of computation 2008-09, Vol.77 (263), p.1755-1778
Main Authors: Bostan, A., Morain, F., Salvy, B., Schost, É.
Format: Article
Language:English
Subjects:
Algebra
Algebraic geometry
Algorithms
Coefficients
Cryptography
Curves
Differential equations
Exact sciences and technology
Mathematics
Methods of scientific computing (including symbolic computation, algebraic computation)
Number theory
Numerical analysis
Numerical analysis. Scientific computation
Polynomials
Power series
Rational functions
Research article
Sciences and techniques of general use
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0025-5718
1088-6842
DOI:10.1090/S0025-5718-08-02066-8