A Memory Efficient Version of Satoh's Algorithm

F Vercauteren; B Preneel; J Vandewalle

doi:10.1007/3-540-44987-6_1

A Memory Efficient Version of Satoh's Algorithm

F Vercauteren, B Preneel, J Vandewalle

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

22 Citations (Scopus)

Abstract

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(n³) memory. Furthermore, our version has the same run time complexity of O(n^n+ε) 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 contribution	A Memory Efficient Version of Satoh's Algorithm
Original language	English
Title of host publication	Advances in Cryptology
Subtitle of host publication	EUROCRYPT 2001 International Conference on the Theory and Application of Cryptographic Techniques Innsbruck, Austria, May 6–10, 2001 Proceedings
Editors	Birgit Pfitzmann
Publisher	Springer
Pages	1-13
Number of pages	13
ISBN (Electronic)	9783540449874
ISBN (Print)	9783540420705
DOIs	https://doi.org/10.1007/3-540-44987-6_1
Publication status	Published - 15 Apr 2001

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	2045
ISSN (Print)	0302-9743

Access to Document

10.1007/3-540-44987-6_1

Handle.net

Persistent link

Cite this

Vercauteren, F., Preneel, B., & Vandewalle, J. (2001). A Memory Efficient Version of Satoh's Algorithm. In B. Pfitzmann (Ed.), Advances in Cryptology: EUROCRYPT 2001 International Conference on the Theory and Application of Cryptographic Techniques Innsbruck, Austria, May 6–10, 2001 Proceedings (pp. 1-13). (Lecture Notes in Computer Science; Vol. 2045). Springer. https://doi.org/10.1007/3-540-44987-6_1

@inproceedings{1660ed9937874e52ace0e64c6a689451,

title = "A Memory Efficient Version of Satoh's Algorithm",

abstract = "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.",

author = "F Vercauteren and B Preneel and J Vandewalle",

year = "2001",

month = apr,

day = "15",

doi = "10.1007/3-540-44987-6_1",

language = "English",

isbn = "9783540420705",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "1--13",

editor = "Birgit Pfitzmann",

booktitle = "Advances in Cryptology",

}

Vercauteren, F, Preneel, B & Vandewalle, J 2001, A Memory Efficient Version of Satoh's Algorithm. in B Pfitzmann (ed.), Advances in Cryptology: EUROCRYPT 2001 International Conference on the Theory and Application of Cryptographic Techniques Innsbruck, Austria, May 6–10, 2001 Proceedings. Lecture Notes in Computer Science, vol. 2045, Springer, pp. 1-13. https://doi.org/10.1007/3-540-44987-6_1

A Memory Efficient Version of Satoh's Algorithm. / Vercauteren, F; Preneel, B; Vandewalle, J.

Advances in Cryptology: EUROCRYPT 2001 International Conference on the Theory and Application of Cryptographic Techniques Innsbruck, Austria, May 6–10, 2001 Proceedings. ed. / Birgit Pfitzmann. Springer, 2001. p. 1-13 (Lecture Notes in Computer Science; Vol. 2045).

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

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 -

Vercauteren F, Preneel B, Vandewalle J. A Memory Efficient Version of Satoh's Algorithm. In Pfitzmann B, editor, Advances in Cryptology: EUROCRYPT 2001 International Conference on the Theory and Application of Cryptographic Techniques Innsbruck, Austria, May 6–10, 2001 Proceedings. Springer. 2001. p. 1-13. (Lecture Notes in Computer Science). doi: 10.1007/3-540-44987-6_1

A Memory Efficient Version of Satoh's Algorithm

Abstract

Publication series

Access to Document

Handle.net

Other files and links

Fingerprint

Cite this