TY - GEN

T1 - A Memory Efficient Version of Satoh's Algorithm

AU - Vercauteren, F

AU - Preneel, B

AU - Vandewalle, J

PY - 2001/4/15

Y1 - 2001/4/15

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

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

UR - http://www.cs.bris.ac.uk/Publications/pub_info.jsp?id=1000611

U2 - 10.1007/3-540-44987-6_1

DO - 10.1007/3-540-44987-6_1

M3 - Conference Contribution (Conference Proceeding)

SN - 9783540420705

T3 - Lecture Notes in Computer Science

SP - 1

EP - 13

BT - Advances in Cryptology

A2 - Pfitzmann, Birgit

PB - Springer

ER -