“Chinese & Match”, an
alternative to Atkin's “Match and Sort” method used in the SEA algorithm.
Mathematics of Computation, 70(234):827-836, April 2001..
A classical way to compute the number of points of elliptic
curves defined over finite fields from partial data obtained
in SEA (Schoof Elkies Atkin) algorithm is a so-called
“Match and Sort” method due to Atkin. This method is a
“baby step/giant step” way to find the number of points
among C candidates with O(sqrt(C)) elliptic curve
additions. Observing that the partial information modulo
Atkin's primes is redundant, we propose to take advantage of
this redundancy to eliminate the usual elliptic curve
algebra in this phase of the SEA computation. This yields an
algorithm of similar complexity, but the space needed is
smaller than what Atkin's method requires. In practice, our
technique amounts to an acceleration of Atkin's method,
allowing us to count the number of points of an elliptic
curve defined over GF(21663). As far as we know, this
is the largest point-counting computation to
date. Furthermore, the algorithm is easily parallelized.
[ bib |