Welcome to the resource topic for 2006/176
Title:
Counting points on elliptic curves in medium characteristic
Authors: Antoine Joux, 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.
ePrint: https://eprint.iacr.org/2006/176
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .