Fast algorithms for computing isogenies between elliptic curves

A. Bostan; F. Morain; B. Salvy; É Schost

doi:10.1090/S0025-5718-08-02066-8

Fast algorithms for computing isogenies between elliptic curves

A. Bostan
, F. Morain
, B. Salvy
, É Schost

Research output: Contribution to journal › Article › peer-review

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 ℓ (ℓ different from the characteristic) in time quasi-linear with respect to ℓ. This is based in particular on fast algorithms for power series expansion of the Weierstrass ℘-function and related functions.

Original language	English
Pages (from-to)	1755-1778
Number of pages	24
Journal	Mathematics of Computation
Volume	77
Issue number	263
DOIs	https://doi.org/10.1090/S0025-5718-08-02066-8
Publication status	Published - 1 Jul 2008
Externally published	Yes

Keywords

Elliptic curves
Fast algorithms
Finite fields
Isogenies
Newton iteration
Schoof-Elkies-Atkin algorithm

Access to Document

10.1090/S0025-5718-08-02066-8

Cite this

@article{a75decbbc6a44bdd8c4baad30a39672c,

title = "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 ℓ (ℓ different from the characteristic) in time quasi-linear with respect to ℓ. This is based in particular on fast algorithms for power series expansion of the Weierstrass ℘-function and related functions.",

keywords = "Elliptic curves, Fast algorithms, Finite fields, Isogenies, Newton iteration, Schoof-Elkies-Atkin algorithm",

author = "A. Bostan and F. Morain and B. Salvy and {\'E} Schost",

year = "2008",

month = jul,

day = "1",

doi = "10.1090/S0025-5718-08-02066-8",

language = "English",

volume = "77",

pages = "1755--1778",

journal = "Mathematics of Computation",

issn = "0025-5718",

number = "263",

}

TY - JOUR

T1 - Fast algorithms for computing isogenies between elliptic curves

AU - Bostan, A.

AU - Morain, F.

AU - Salvy, B.

AU - Schost, É

PY - 2008/7/1

Y1 - 2008/7/1

N2 - 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 ℓ (ℓ different from the characteristic) in time quasi-linear with respect to ℓ. This is based in particular on fast algorithms for power series expansion of the Weierstrass ℘-function and related functions.

AB - 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 ℓ (ℓ different from the characteristic) in time quasi-linear with respect to ℓ. This is based in particular on fast algorithms for power series expansion of the Weierstrass ℘-function and related functions.

KW - Elliptic curves

KW - Fast algorithms

KW - Finite fields

KW - Isogenies

KW - Newton iteration

KW - Schoof-Elkies-Atkin algorithm

U2 - 10.1090/S0025-5718-08-02066-8

DO - 10.1090/S0025-5718-08-02066-8

M3 - Article

AN - SCOPUS:47249102588

SN - 0025-5718

VL - 77

SP - 1755

EP - 1778

JO - Mathematics of Computation

JF - Mathematics of Computation

IS - 263

ER -

Fast algorithms for computing isogenies between elliptic curves

Abstract

Keywords

Access to Document

Fingerprint

Cite this