Paper 2008/060

Fast Algorithms for Arithmetic on Elliptic Curves Over Prime Fields

Nicholas T. Sullivan

Abstract

We present here a thorough discussion of the problem of fast arithmetic on elliptic curves over prime order finite fields. Since elliptic curves were independently pro- posed as a setting for cryptography by Koblitz [53] and Miller [67], the group of points on an elliptic curve has been widely used for discrete logarithm based cryptosystems. In this thesis, we survey, analyse and compare the fastest known serial and parallel algorithms for elliptic curve scalar multiplication, the primary operation in discrete logarithm based cryptosystems. We also introduce some new algorithms for the basic group operation and several new parallel scalar multiplication algorithms. We present a mathematical basis for comparing the various algorithms and make recommendations for the fastest algorithms to use in different circumstances.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Thesis, University of Calgary, 2007
Keywords
Elliptic Curve Cryptography
Contact author(s)
nicholas sullivan @ gmail com
History
2008-02-11: received
Short URL
https://ia.cr/2008/060
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/060,
      author = {Nicholas T.  Sullivan},
      title = {Fast Algorithms for Arithmetic on Elliptic Curves Over Prime Fields},
      howpublished = {Cryptology ePrint Archive, Paper 2008/060},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/060}},
      url = {https://eprint.iacr.org/2008/060}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.