We discuss multidoubling methods for efficient elliptic scalar multiplication. The methods allows computation of 2k P directly from P without computing the intermediate points, where P denotes a randomly selected point on an elliptic curve. We introduce algorithms for elliptic curves with Montgomery form and Weierstrass form defined over finite fields with characteristic greater than 3 in terms of affine coordinates. These algorithms are faster than k repeated doublings. Moreover, we apply the algorithms to scalar multiplication on elliptic curves and analyze computational complexity. As a result of our implementation with respect to the Montgomery and Weierstrass forms in terms of affine coordinates, we achieved running time reduced by 28% and 31%, respectively, in the scalar multiplication of an elliptic curve of size 160-bit over finite fields with characteristic greater than 3.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Yasuyuki SAKAI, Kouichi SAKURAI, "Speeding Up Elliptic Scalar Multiplication Using Multidoubling" in IEICE TRANSACTIONS on Fundamentals,
vol. E85-A, no. 5, pp. 1075-1083, May 2002, doi: .
Abstract: We discuss multidoubling methods for efficient elliptic scalar multiplication. The methods allows computation of 2k P directly from P without computing the intermediate points, where P denotes a randomly selected point on an elliptic curve. We introduce algorithms for elliptic curves with Montgomery form and Weierstrass form defined over finite fields with characteristic greater than 3 in terms of affine coordinates. These algorithms are faster than k repeated doublings. Moreover, we apply the algorithms to scalar multiplication on elliptic curves and analyze computational complexity. As a result of our implementation with respect to the Montgomery and Weierstrass forms in terms of affine coordinates, we achieved running time reduced by 28% and 31%, respectively, in the scalar multiplication of an elliptic curve of size 160-bit over finite fields with characteristic greater than 3.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e85-a_5_1075/_p
Copy
@ARTICLE{e85-a_5_1075,
author={Yasuyuki SAKAI, Kouichi SAKURAI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Speeding Up Elliptic Scalar Multiplication Using Multidoubling},
year={2002},
volume={E85-A},
number={5},
pages={1075-1083},
abstract={We discuss multidoubling methods for efficient elliptic scalar multiplication. The methods allows computation of 2k P directly from P without computing the intermediate points, where P denotes a randomly selected point on an elliptic curve. We introduce algorithms for elliptic curves with Montgomery form and Weierstrass form defined over finite fields with characteristic greater than 3 in terms of affine coordinates. These algorithms are faster than k repeated doublings. Moreover, we apply the algorithms to scalar multiplication on elliptic curves and analyze computational complexity. As a result of our implementation with respect to the Montgomery and Weierstrass forms in terms of affine coordinates, we achieved running time reduced by 28% and 31%, respectively, in the scalar multiplication of an elliptic curve of size 160-bit over finite fields with characteristic greater than 3.},
keywords={},
doi={},
ISSN={},
month={May},}
Copy
TY - JOUR
TI - Speeding Up Elliptic Scalar Multiplication Using Multidoubling
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1075
EP - 1083
AU - Yasuyuki SAKAI
AU - Kouichi SAKURAI
PY - 2002
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E85-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2002
AB - We discuss multidoubling methods for efficient elliptic scalar multiplication. The methods allows computation of 2k P directly from P without computing the intermediate points, where P denotes a randomly selected point on an elliptic curve. We introduce algorithms for elliptic curves with Montgomery form and Weierstrass form defined over finite fields with characteristic greater than 3 in terms of affine coordinates. These algorithms are faster than k repeated doublings. Moreover, we apply the algorithms to scalar multiplication on elliptic curves and analyze computational complexity. As a result of our implementation with respect to the Montgomery and Weierstrass forms in terms of affine coordinates, we achieved running time reduced by 28% and 31%, respectively, in the scalar multiplication of an elliptic curve of size 160-bit over finite fields with characteristic greater than 3.
ER -