Links 


 [JL06a] 
A. Joux and R. Lercier. 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(l^{2}(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(log^{4} q) and a space complexity
O(log^{2} 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 log^{2} q factor.
[ bib 
preprint 
publication ]
Back 

