Refined Computations for Points of the Form 2kP Based on Montgomery Trick

Daisuke ADACHI  Tomio HIRATA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E89-A   No.1   pp.334-339
Publication Date: 2006/01/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e89-a.1.334
Print ISSN: 0916-8508
Type of Manuscript: LETTER
Category: Information Security
Keyword: 
scalar multiplication,  elliptic curve arithmetic,  Montgomery trick,  window method,  

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




Summary: 
This paper focuses on algorithms for an efficient scalar multiplication. It proposes two algorithms for computing points of the form 2kP in affine coordinates. One works for k=2, and the other works for an arbitrary natural number k. The efficiency of these algorithms is based on a trade-off between a field inversion and several field multiplications. Montgomery trick is used to implement this trade-off. Since a field inversion is usually more expensive than 10 field multiplications, the proposed algorithms are efficient in comparison with existing ones.