Paper 2006/176 Original: eprint.iacr.org/2006/176 ↗
Counting points on elliptic curves in medium characteristic
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.
Metadata
- Available format(s)
PDF- Category
- Public-key cryptography
- Publication info
- Preprint.
- History
- 2006-05-22: last updated
- 2006-05-22: published
- Short URL
- https://ia.cr/2006/176
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}