Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Computing isogenies between elliptic curves
over $F_{p^n}$ using Couveignes's algorithm

Authors: R. Lercier and F. Morain
Journal: Math. Comp. 69 (2000), 351-370
MSC (1991): Primary 11G20; Secondary 11T71, 94A60, 11Y16
Published electronically: March 4, 1999
MathSciNet review: 1642770
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The heart of the improvements by Elkies to Schoof's algorithm for computing the cardinality of elliptic curves over a finite field is the ability to compute isogenies between curves. Elkies' approach is well suited for the case where the characteristic of the field is large. Couveignes showed how to compute isogenies in small characteristic. The aim of this paper is to describe the first successful implementation of Couveignes's algorithm. In particular, we describe the use of fast algorithms for performing incremental operations on series. We also insist on the particular case of the characteristic 2.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 11G20, 11T71, 94A60, 11Y16

Retrieve articles in all journals with MSC (1991): 11G20, 11T71, 94A60, 11Y16

Additional Information

R. Lercier
Affiliation: CELAR/SSIG, Route de Laillé, F-35170 Bruz, France

F. Morain
Affiliation: Laboratoire d’Informatique de l’École polytechnique (LIX - UMR 7650), F-91128 Palaiseau Cedex, France

Keywords: Elliptic curves, finite fields, isogenies, formal groups, Schoof's algorithm
Received by editor(s): May 6, 1996
Received by editor(s) in revised form: March 10, 1998
Published electronically: March 4, 1999
Additional Notes: The second author is on leave from the French Department of Defense, Délégation Générale pour l’Armement
Article copyright: © Copyright 1999 American Mathematical Society