Cryptology ePrint Archive: Report 2002/112

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

Kirsten Eisentraeger, Kristin Lauter, and Peter L. Montgomery

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

Category / Keywords: implementation / elliptic curve cryptosystem, Weil pairing, Tate pairing

Publication Info: submitted for publication

Date: received 5 Aug 2002

Contact author: klauter at microsoft com

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

Version: 20020810:133033 (All versions of this report)

Short URL: ia.cr/2002/112

Discussion forum: Show discussion | Start new discussion