Title: A Memory Efficient Version of Satoh's Algorithm
Authors: Vercauteren, Fr├ęderik ×
Preneel, Bart
Vandewalle, Joos #
Issue Date: 2001
Publisher: Springer
Series Title: Lecture Notes in Computer Science vol:2045 pages:1-13
Conference: EUROCRYPT 2001 date:May 06-10, 2001
Abstract: In this paper we present an algorithm for counting points on elliptic curves over a finite field F(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+epsilon)) 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.
ISSN: 0302-9743
Publication status: published
KU Leuven publication type: IT
Appears in Collections:ESAT - STADIUS, Stadius Centre for Dynamical Systems, Signal Processing and Data Analytics
× corresponding author
# (joint) last author

Files in This Item:
File Status SizeFormat
article-84.pdf Published 213KbAdobe PDFView/Open Request a copy

These files are only available to some KU Leuven Association staff members


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science