# zbMATH — the first resource for mathematics

Counting points on elliptic curves over finite fields of small characteristic in quasi quadratic time. (English) Zbl 1035.11067
Biham, Eli (ed.), Advances in cryptology – EUROCRYPT 2003. International conference on the theory and applications of cryptographic techniques, Warsaw, Poland, May 4–8, 2003. Proceedings. Berlin: Springer (ISBN 3-540-14039-5/pbk). Lect. Notes Comput. Sci. 2656, 360-373 (2003).
Summary: Let $$p$$ be a small prime and $$q=p^n$$. Let $$E$$ be an elliptic curve over $$\mathbb {F}_q$$. We propose an algorithm which computes without any preprocessing the $$j$$-invariant of the canonical lift of $$E$$ with the cost of $$O(\log n)$$ times the cost needed to compute a power of the lift of the Frobenius. Let $$\mu$$ be a constant so that the product of two $$n$$-bit length integers can be carried out in $$O(n^\mu)$$ bit operations. This yields an algorithm to compute the number of points on elliptic curves which reaches, at the expense of a $$O(n^{\frac{5}{2}})$$ space complexity, a theoretical time complexity bound equal to $$O(n^{\max(1.19, \mu)+\mu+\frac{1}{2}}\log n)$$. When the field has got a Gaussian Normal Basis of small type, we obtain furthermore an algorithm with $$O(\log(n)n^{2\mu})$$ time and $$O(n^2)$$ space complexities. From a practical viewpoint, the corresponding algorithm is particularly well suited for implementations. We outline this by a 100002-bit computation.
For the entire collection see [Zbl 1020.00023].

##### MSC:
 11Y16 Number-theoretic algorithms; complexity 11G07 Elliptic curves over local fields 14G50 Applications to coding theory and cryptography of arithmetic geometry 94A60 Cryptography
##### Keywords:
Elliptic curves; canonical lifts; AGM
Full Text: