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

Vercauteren, Frederik; Preneel, Bart; Vandewalle, Joos

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

MSC:

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

Keywords:

finite field of small characteristic; algorithm; counting points on elliptic curves; Satoh’s algorithm

Citations:

Zbl 1009.11052