A Memory Efficient Version of Satoh's Algorithm

F Vercauteren, B Preneel, J Vandewalle

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

22 Citations (Scopus)


In this paper we present an algorithm for counting points on elliptic curves over a finite field Fpn of small characteristic, based on Satoh's algorithm. The memory requirement of our algorithm is O(n2), where Satoh's original algorithm needs O(n3) memory. Furthermore, our version has the same run time complexity of O(nn+ε) 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.
Translated title of the contributionA Memory Efficient Version of Satoh's Algorithm
Original languageEnglish
Title of host publicationAdvances in Cryptology
Subtitle of host publicationEUROCRYPT 2001 International Conference on the Theory and Application of Cryptographic Techniques Innsbruck, Austria, May 6–10, 2001 Proceedings
EditorsBirgit Pfitzmann
Number of pages13
ISBN (Electronic)9783540449874
ISBN (Print)9783540420705
Publication statusPublished - 15 Apr 2001

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Dive into the research topics of 'A Memory Efficient Version of Satoh's Algorithm'. Together they form a unique fingerprint.

Cite this