## 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].

### MSC:

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