Skip to main content

A Memory Efficient Version of Satoh's Algorithm

Frederik Vercauteren, Bart Preneel, Joos Vandewalle, A Memory Efficient Version of Satoh's Algorithm. Advances in Cryptology - Eurocrypt 2001. Birgit Pfitzmann, (eds.). ISSN 0302-9743, pp. 1–13. May 2001. No electronic version available.


In this paper we present an algorithm for counting points on elliptic curves over a finite field $\FF_p^n$ of small characteristic, based on Satoh's algorithm. The memory requirement of our algorithm is $O(n^2)$, where Satoh's original algorithm needs $O(n^3)$ memory. Furthermore, our version has the same run time complexity of $O(n^3 + arepsilon)$ 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.

Bibtex entry.

Contact details

Publication Admin