International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

An Efficient Procedure to Double and Add Points on an Elliptic Curve

Authors:
Kirsten Eisenträger
Kristin E. Lauter
Peter L. Montgomery
Download:
URL: http://eprint.iacr.org/2002/112
Search ePrint
Search Google
Abstract: We present an algorithm that speeds exponentiation on a general elliptic curve by an estimated 3.8% to 8.5% over the best known general exponentiation methods when using affine coordinates. This is achieved by eliminating a field multiplication when we compute 2P + Q from given points P, Q on the curve. We give applications to simultaneous multiple exponentiation and to the Elliptic Curve Method of factorization. We show how this improvement together with another idea can speed the computation of the Weil and Tate pairings by up to 7.8%.
BibTeX
@misc{eprint-2002-11635,
  title={An Efficient Procedure to Double and Add Points on an Elliptic Curve},
  booktitle={IACR Eprint archive},
  keywords={implementation / elliptic curve cryptosystem, Weil pairing, Tate pairing},
  url={http://eprint.iacr.org/2002/112},
  note={submitted for publication klauter@microsoft.com 11904 received 5 Aug 2002},
  author={Kirsten Eisenträger and Kristin E. Lauter and Peter L. Montgomery},
  year=2002
}