A Signed Binary Window Method for Fast Computing over Elliptic Curves
Summary :
The basic operation in elliptic cryptosystems is the computation of a multiple d・P of a point P on the elliptic curve modulo n. We propose a fast and systematic method of reducing the number of operations over elliptic curves. The proposed method is based on pre-computation to generate an adequate addition-subtraction chain for multiplier the d. By increasing the average length of zero runs in a signed binary representation of d, we can speed up the window method. Formulating the time complexity of the proposed method makes clear that the proposed method is faster than other methods. For example, for d with length 512 bits, the proposed method requires 602.6 multiplications on average. Finally, we point out that each addition/subtraction over the elliptic curve using homogeneous coordinates can be done in 3 multiplications if parallel processing is allowed.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E76-A No.1 pp.55-62
- Publication Date
- 1993/01/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on Cryptography and Information Security)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
Kenji KOYAMA, Yukio TSURUOKA, "A Signed Binary Window Method for Fast Computing over Elliptic Curves" in IEICE TRANSACTIONS on Fundamentals,
vol. E76-A, no. 1, pp. 55-62, January 1993, doi: .
Abstract: The basic operation in elliptic cryptosystems is the computation of a multiple d・P of a point P on the elliptic curve modulo n. We propose a fast and systematic method of reducing the number of operations over elliptic curves. The proposed method is based on pre-computation to generate an adequate addition-subtraction chain for multiplier the d. By increasing the average length of zero runs in a signed binary representation of d, we can speed up the window method. Formulating the time complexity of the proposed method makes clear that the proposed method is faster than other methods. For example, for d with length 512 bits, the proposed method requires 602.6 multiplications on average. Finally, we point out that each addition/subtraction over the elliptic curve using homogeneous coordinates can be done in 3 multiplications if parallel processing is allowed.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e76-a_1_55/_p
Copy
@ARTICLE{e76-a_1_55,
author={Kenji KOYAMA, Yukio TSURUOKA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Signed Binary Window Method for Fast Computing over Elliptic Curves},
year={1993},
volume={E76-A},
number={1},
pages={55-62},
abstract={The basic operation in elliptic cryptosystems is the computation of a multiple d・P of a point P on the elliptic curve modulo n. We propose a fast and systematic method of reducing the number of operations over elliptic curves. The proposed method is based on pre-computation to generate an adequate addition-subtraction chain for multiplier the d. By increasing the average length of zero runs in a signed binary representation of d, we can speed up the window method. Formulating the time complexity of the proposed method makes clear that the proposed method is faster than other methods. For example, for d with length 512 bits, the proposed method requires 602.6 multiplications on average. Finally, we point out that each addition/subtraction over the elliptic curve using homogeneous coordinates can be done in 3 multiplications if parallel processing is allowed.},
keywords={},
doi={},
ISSN={},
month={January},}
Copy
TY - JOUR
TI - A Signed Binary Window Method for Fast Computing over Elliptic Curves
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 55
EP - 62
AU - Kenji KOYAMA
AU - Yukio TSURUOKA
PY - 1993
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E76-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 1993
AB - The basic operation in elliptic cryptosystems is the computation of a multiple d・P of a point P on the elliptic curve modulo n. We propose a fast and systematic method of reducing the number of operations over elliptic curves. The proposed method is based on pre-computation to generate an adequate addition-subtraction chain for multiplier the d. By increasing the average length of zero runs in a signed binary representation of d, we can speed up the window method. Formulating the time complexity of the proposed method makes clear that the proposed method is faster than other methods. For example, for d with length 512 bits, the proposed method requires 602.6 multiplications on average. Finally, we point out that each addition/subtraction over the elliptic curve using homogeneous coordinates can be done in 3 multiplications if parallel processing is allowed.
ER -
English
