Counting Points on Elliptic Curves In Medium Characteristic

In this paper, we revisit the problem of computing the kernel of a separable isogeny of degree # between two elliptic curves defined over a finite field Fq of characteristic p. We describe an algorithm the asymptotic time complexity of which is equal to (1 + #/p) log q) bit operations. This algorithm is particularly useful when # > 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 in the previously unfavorable case where p log q. Compared to the best previous algorithms, the memory requirements of our SEA variation are smaller by a log²q factor