Isogeny cycles and the Schoof-Elkies-Atkin algorithm
Jean-Marc Couveignes · 1996
. 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 `. Elkies and Atkin have designed practical improvements to the basic algorithm, that make use of "good" primes `. 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. We investigate the properties of the "isogeny cycles" that appear. 1. Introduction Let E be an elliptic curve over a finite field F q where q = p r , p prime. The curve is given by some equation E(X; Y ) = 0 in Weierstrass form E(X; Y ) = Y 2 + a 1 XY + a 3 Y \\Gamma (X 3 + a 2 X 2 + a 4 X + a 6 ) so that a generic point on the curve is given by (X; Y ) mod E . Let m be the number of points of E. It is well known that m = q + 1 \\Gamma t, with t an integer satisfying jtj 2 p q. If q is small the problem of computing the cardinality of E is easy: one can simply enumerate all the p...