Treffer: Fast algorithms for computing isogenies between elliptic curves

Title:
Fast algorithms for computing isogenies between elliptic curves
Authors:
Bostan, Alin, Salvy, Bruno, Morain, Francois, Schost, Eric
Contributors:
Algorithms (ALGO), Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X), Institut Polytechnique de Paris (IP Paris)-Institut Polytechnique de Paris (IP Paris)-Centre National de la Recherche Scientifique (CNRS), Algorithmic number theory for cryptology (TANC), Institut Polytechnique de Paris (IP Paris)-Institut Polytechnique de Paris (IP Paris)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), Institut Polytechnique de Paris (IP Paris)-Institut Polytechnique de Paris (IP Paris)-Centre National de la Recherche Scientifique (CNRS)-Centre Inria de Saclay
Source:
[Research Report] 2006. :28-28
Publisher Information:
CCSD, 2006.
Publication Year:
2006
Collection:
collection:X
collection:CNRS
collection:INRIA
collection:INRIA-ROCQ
collection:LIX
collection:INRIA-SACLAY
collection:X-LIX
collection:X-DEP
collection:X-DEP-INFO
collection:INRIA_TEST
collection:TESTALAIN1
collection:INRIA2
collection:LARA
collection:INRIA-300009
Subject Terms:
Fast algorithms, elliptic curves, finite fields, isogenies, Schoof-Elkies-Atkin algorithm, Newton iteration, ACM: G.: Mathematics of Computing, G.4: MATHEMATICAL SOFTWARE, G.4.0: Algorithm design and analysis, [INFO.INFO-CC]Computer Science [cs], Computational Complexity [cs.CC], [INFO.INFO-DS]Computer Science [cs], Data Structures and Algorithms [cs.DS], [INFO.INFO-SC]Computer Science [cs], Symbolic Computation [cs.SC], [MATH.MATH-NT]Mathematics [math], Number Theory [math.NT]
Original Identifier:
ARXIV: cs.CC/0609020
HAL:
Document Type:
Report report<br />Reports
Language:
English
Relation:
info:eu-repo/semantics/altIdentifier/arxiv/cs.CC/0609020
Access URL:
https://inria.hal.science/inria-00091441
https://inria.hal.science/inria-00091441v1/document
https://inria.hal.science/inria-00091441v1/file/BoMoSaSc06.pdf
Rights:
info:eu-repo/semantics/OpenAccess
Accession Number:
edshal.inria.00091441v1
Database:
HAL

Weitere Informationen

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.