Schoof’s algorithm and isogeny cycles

Jean Marc Couveignes; François Morain

doi:10.1007/3-540-58691-1_42

Schoof’s algorithm and isogeny cycles

Jean Marc Couveignes
, François Morain

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

The heart of Schoof’s algorithm for computing the cardinality m of an elliptic curve over a finite field is the computation of m modulo small primes l. Elkies and Atkin have designed practical improvements to the basic algorithm, that make use of “good” primes l. We show how to use powers of good primes in an efficient way. This is done by computing isogenies between curves over the ground field. A new structure appears, called “isogeny cycle”. We investigate some properties of this structure.

Original language	English
Title of host publication	Algorithmic Number Theory - 1st International Symposium, ANTS-I, Proceedings
Editors	Leonard M. Adleman, Ming-Deh Huang
Publisher	Springer Verlag
Pages	43-58
Number of pages	16
ISBN (Print)	9783540586913
DOIs	https://doi.org/10.1007/3-540-58691-1_42
Publication status	Published - 1 Jan 1994
Event	1st Algorithmic Number Thoery Symposium, ANTS-I 1994 - Ithaca, United States Duration: 6 May 1994 → 9 May 1994

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	877 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	1st Algorithmic Number Thoery Symposium, ANTS-I 1994
Country/Territory	United States
City	Ithaca
Period	6/05/94 → 9/05/94

Access to Document

10.1007/3-540-58691-1_42

Cite this

Couveignes, J. M., & Morain, F. (1994). Schoof’s algorithm and isogeny cycles. In L. M. Adleman, & M.-D. Huang (Eds.), Algorithmic Number Theory - 1st International Symposium, ANTS-I, Proceedings (pp. 43-58). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 877 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-58691-1_42

Couveignes, Jean Marc ; Morain, François. / Schoof’s algorithm and isogeny cycles. Algorithmic Number Theory - 1st International Symposium, ANTS-I, Proceedings. editor / Leonard M. Adleman ; Ming-Deh Huang. Springer Verlag, 1994. pp. 43-58 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{83cc4b782ce04cf0ba1073f10cc5dd32,

title = "Schoof{\textquoteright}s algorithm and isogeny cycles",

abstract = "The heart of Schoof{\textquoteright}s algorithm for computing the cardinality m of an elliptic curve over a finite field is the computation of m modulo small primes l. Elkies and Atkin have designed practical improvements to the basic algorithm, that make use of “good” primes l. We show how to use powers of good primes in an efficient way. This is done by computing isogenies between curves over the ground field. A new structure appears, called “isogeny cycle”. We investigate some properties of this structure.",

author = "Couveignes, \{Jean Marc\} and Fran{\c c}ois Morain",

year = "1994",

month = jan,

day = "1",

doi = "10.1007/3-540-58691-1\_42",

language = "English",

isbn = "9783540586913",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "43--58",

editor = "Adleman, \{Leonard M.\} and Ming-Deh Huang",

booktitle = "Algorithmic Number Theory - 1st International Symposium, ANTS-I, Proceedings",

}

Couveignes, JM & Morain, F 1994, Schoof’s algorithm and isogeny cycles. in LM Adleman & M-D Huang (eds), Algorithmic Number Theory - 1st International Symposium, ANTS-I, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 877 LNCS, Springer Verlag, pp. 43-58, 1st Algorithmic Number Thoery Symposium, ANTS-I 1994, Ithaca, United States, 6/05/94. https://doi.org/10.1007/3-540-58691-1_42

Schoof’s algorithm and isogeny cycles. / Couveignes, Jean Marc; Morain, François.
Algorithmic Number Theory - 1st International Symposium, ANTS-I, Proceedings. ed. / Leonard M. Adleman; Ming-Deh Huang. Springer Verlag, 1994. p. 43-58 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 877 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Schoof’s algorithm and isogeny cycles

AU - Couveignes, Jean Marc

AU - Morain, François

PY - 1994/1/1

Y1 - 1994/1/1

N2 - The heart of Schoof’s algorithm for computing the cardinality m of an elliptic curve over a finite field is the computation of m modulo small primes l. Elkies and Atkin have designed practical improvements to the basic algorithm, that make use of “good” primes l. We show how to use powers of good primes in an efficient way. This is done by computing isogenies between curves over the ground field. A new structure appears, called “isogeny cycle”. We investigate some properties of this structure.

AB - The heart of Schoof’s algorithm for computing the cardinality m of an elliptic curve over a finite field is the computation of m modulo small primes l. Elkies and Atkin have designed practical improvements to the basic algorithm, that make use of “good” primes l. We show how to use powers of good primes in an efficient way. This is done by computing isogenies between curves over the ground field. A new structure appears, called “isogeny cycle”. We investigate some properties of this structure.

UR - https://www.scopus.com/pages/publications/0007436447

U2 - 10.1007/3-540-58691-1_42

DO - 10.1007/3-540-58691-1_42

M3 - Conference contribution

AN - SCOPUS:0007436447

SN - 9783540586913

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 43

EP - 58

BT - Algorithmic Number Theory - 1st International Symposium, ANTS-I, Proceedings

A2 - Adleman, Leonard M.

A2 - Huang, Ming-Deh

PB - Springer Verlag

T2 - 1st Algorithmic Number Thoery Symposium, ANTS-I 1994

Y2 - 6 May 1994 through 9 May 1994

ER -

Couveignes JM, Morain F. Schoof’s algorithm and isogeny cycles. In Adleman LM, Huang MD, editors, Algorithmic Number Theory - 1st International Symposium, ANTS-I, Proceedings. Springer Verlag. 1994. p. 43-58. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-58691-1_42

Schoof’s algorithm and isogeny cycles

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this