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

INRIA Rocquencourt
Université Paris-Saclay
DGA-MI
University of Western Ontario

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

Résumé

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.

langue originale	Anglais
Pages (de - à)	1755-1778
Nombre de pages	24
journal	Mathematics of Computation
Volume	77
Numéro de publication	263
Les DOIs	https://doi.org/10.1090/S0025-5718-08-02066-8
état	Publié - 1 juil. 2008
Modification externe	Oui

Accès au document

10.1090/S0025-5718-08-02066-8

Contient cette citation

@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

Résumé

Accès au document

Empreinte digitale

Contient cette citation