Counting points on elliptic curves in medium characteristic

Antoine Joux; Reynald Lercier

Paper 2006/176

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 $ℓ$ 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 (ℓ^{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 . More precisely, we obtain a heuristic time complexity and a space complexity , in the previously unfavorable case where . Compared to the best previous algorithms, the memory requirements of our SEA variation are smaller by a factor.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: elliptic curve cryptosystem
Contact author(s): reynald lercier @ m4x org
History: 2006-05-22: received
Short URL: https://ia.cr/2006/176
License: CC BY

BibTeX

@misc{cryptoeprint:2006/176,
      author = {Antoine Joux and Reynald Lercier},
      title = {Counting points on elliptic curves in medium characteristic},
      howpublished = {Cryptology {ePrint} Archive, Paper 2006/176},
      year = {2006},
      url = {https://eprint.iacr.org/2006/176}
}