Previous [1] [2] [3] [4] [5] [6] [7] [8]

Journal of Inforamtion Science and Engineering, Vol.11 No.2, pp.295-305 (June 1995)
Shortest Weighted Length Addition Chains

Yuh-Jiun Chen, Chin-Chen Chang*and Wei-Pang Yang#
Institute of Computer Science and Information Engineering
National Chiao Tung University
Hsinchu, Taiwan, R.O.C.
*Institute of Computer Science and Information Engineering
National Chung Cheng University
Chiayi, Taiwan, 621, R.O.C.
#Institute of Computer and Information Science
National Chiao Tung University
Hsinchu, 300, Taiwan, R.O.C.

This paper presents the concept of shortest weighted length addition chains. This concept is a generalization of the concept of conventional shortest addition chains. The proposed shortest weighted length addition chain approach is an efficient way to compute an exponentiation xn by using only square operations and multiplication operations. Some distinctive characteristics of shortest weighted length addition chains are proposed, and the correctness is also shown.

Keywords: exponentiation, addition chain, the shortest addition chain, the shortest weighted length addition chain

Received June 7, 1994; revised November 21, 1994.
Communicated by Jhing-Fa Wang.