Counting points on
elliptic curves in medium characteristic.
Cryptology ePrint Archive, Report 2006/176, May 2006..
In this paper, we revisit the problem of computing the
kernel of a separable isogeny of degree l between two
elliptic curves defined over a finite field GF(q) of
characteristic p. We describe an algorithm the asymptotic
time complexity of which is close to O(l2(1+l / p)logq)
bit operations. This algorithm is particularly useful when
l > p and as a consequence, we obtain an improvement of
the complexity of the SEA point counting algorithm for small
values of p. More precisely, we obtain a heuristic time
complexity close to O(log4 q) and a space complexity
O(log2 q), in the previously unfavorable case where
p is close to logq. Compared to the best previous
algorithms, the memory requirements of our SEA variation are
smaller by a log2 q factor.
[ bib |