A memory efficient version of Satoh’s algorithm. (English) Zbl 1009.11052

Pfitzmann, Birgit (ed.), Advances in cryptology - EUROCRYPT 2001. 20th international conference on theory and application of cryptographic techniques, Innsbruck, Austria, May 6-10, 2001. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2045, 1-13 (2001).
Summary: We present an algorithm for counting points on elliptic curves over a finite field \(\mathbb{F}_{p^n}\) of small characteristic, based on Satoh’s algorithm [T. Satoh, J. Ramanujan Math. Soc. 15, 247-270 (2000; Zbl 1009.11052)]. The memory requirement of our algorithm is \(O(n^2)\), whereas Satoh’s original algorithm needs \(O(n^3)\) memory. Furthermore, our version has the same run time complexity of \(O(n^{3+\varepsilon})\) bit operations, but is faster by a constant factor. We give a detailed description of the algorithm in characteristic 2 and show that the amount of memory needed for the generation of a secure 200-bit elliptic curve is within the range of current smart card technology.
For the entire collection see [Zbl 0961.00037].


11G20 Curves over finite and local fields
11Y16 Number-theoretic algorithms; complexity
14G15 Finite ground fields in algebraic geometry


Zbl 1009.11052