3 Université de Versailles St-Quentin-en-Yvelines PRISM

Abstract. 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 eO(`2(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 eO(log4 q) and a space complexity O(log2 q), 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 log2 q factor