Cryptology ePrint Archive: Report 2003/088

Elliptic Curve Point Multiplication

A.G.Rostovtsev and E.B.Makhovenko

Abstract: A method for elliptic curve point multiplication is proposed with complex multiplication by Sqrt[-2] or by (1+Sqrt[-7])/2 instead of point duplication, speeding up multiplication about 1.34 times. Higher radix makes it possible to use one point duplication instead of two and to speed up computation about 1.6 times. We employ prime group order factorization in corresponding quadratic order and integer exponent reduction modulo quadratic prime in the Euclidean imaginary quadratic ring.

Category / Keywords: implementation / elliptic curve cryptosystem; complex multiplication; fast algorithms

Date: received 5 May 2003

Contact author: rostovtsev at ssl stu neva ru

Available format(s): PDF | BibTeX Citation

Version: 20030507:184213 (All versions of this report)

Short URL: ia.cr/2003/088

Discussion forum: Show discussion | Start new discussion