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

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