On \(p\)-adic point counting algorithms for elliptic curves over finite fields. (English) Zbl 1058.11043

Fieker, Claus (ed.) et al., Algorithmic number theory. 5th international symposium, ANTS-V, Sydney, Australia, July 7–12, 2002. Proceedings. Berlin: Springer (ISBN 3-540-43863-7). Lect. Notes Comput. Sci. 2369, 43-66 (2002).
Summary: Let \(p\) be a prime and let \(q := p^{N}\). Let \(E\) be an elliptic curve over \({\mathbb F}_q\). We are interested in efficient algorithms to compute the order of the group \(E({\mathbb F}_q)\) of \({\mathbb F}_q\)-rational points of \(E\). An \(l\)-adic algorithm, known as the SEA algorithm, computes \(\#E({\mathbb F}_q)\) with \(O((\log q)^{{4 +\varepsilon}})\) bit operations (with fast arithmetic) and \(O((\log q)^{2})\) memory. In this article, we survey recent advances in \(p\)-adic algorithms. For a fixed small \(p\), the computational complexity of the known fastest \(p\)-adic point counting algorithm is \(O(N^{{3 +\varepsilon}})\) in time and \(O(N^{2})\) in space. If we accept some precomputation depending only on \(p\) and \(N\) or a certain restriction on \(N\), the time complexity is reduced to \(O(N^{{2.5 +\varepsilon}})\) still with \(O(N^{2})\) space requirement.
For the entire collection see [Zbl 0992.00024].


11G20 Curves over finite and local fields
11Y16 Number-theoretic algorithms; complexity
Full Text: Link