Reynald Lercier

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²(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⁴ q) and a space complexity O(log² 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² q factor.

[ bib | preprint | publication ] Back