Algorithms for computing isogenies between elliptic curves
Reynald Lercier, François Morain · AMS/IP studies in advanced mathematics · 1997
. The efficient implementation of Schoof's algorithm for computing the cardinality of elliptic curves over finite fields requires the computation of isogenies between elliptic curves. We make a survey of algorithms used for accomplishing this task. When the characteristic of the field is large, Weierstrass's functions can be used. When the characteristic of the field is small, we now have three algorithms at our disposal, two due to Couveignes and one to the first author. We treat the same example using these three algorithms and make some comparisons between them. 1. Introduction The motivation for this article is the so-called Schoof-Elkies-Atkin algorithm that computes the cardinality of an elliptic curve over any finite field. The improvements due to Elkies and Atkin require the ability to compute isogenies of prime degree ` between elliptic curves. The first method for doing this uses the Weierstrass's parametrization of elliptic curves and cannot work when the characteristic p ...