**Counting points on elliptic curves in medium characteristic**

*Antoine Joux and Reynald Lercier*

**Abstract: **In this paper, we revisit the problem of computing the kernel of a separable isogeny of degree $\ell$ 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
equal to $\SoftO(\ell^2(1+\ell/p)\log q)$ bit operations. This
algorithm is particularly useful when $\ell > 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 $\SoftO(\log^{4} q)$ and a space
complexity $O(\log^{2} q)$, in the previously unfavorable case where
$p \simeq \log q$. Compared to the best previous algorithms, the
memory requirements of our SEA variation are smaller by a $\log^2 q$
factor.

**Category / Keywords: **public-key cryptography / elliptic curve cryptosystem

**Date: **received 19 May 2006

**Contact author: **reynald lercier at m4x org

**Available format(s): **PDF | BibTeX Citation

**Version: **20060522:130905 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]