Efficient Scalar Multiplications on Elliptic Curves with Direct Computations of Several Doublings

Yasuyuki SAKAI  Kouichi SAKURAI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E84-A   No.1   pp.120-129
Publication Date: 2001/01/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
elliptic curve cryptosystem,  scalar multiplication,  window method,  coordinate system,  implementation,  

Full Text: PDF(248.6KB)>>
Buy this Article

We introduce efficient algorithms for scalar multiplication on elliptic curves defined over FP. The algorithms compute 2k P directly from P, where P is a random point on an elliptic curve, without computing the intermediate points, which is faster than k repeated doublings. Moreover, we apply the algorithms to scalar multiplication on elliptic curves, and analyze their computational complexity. As a result of their implementation with respect to affine (resp. weighted projective) coordinates, we achieved an increased performance factor of 1.45 (45%) (resp. 1.15 (15%)) in the scalar multiplication of the elliptic curve of size 160-bit.