New Methods for Generating Short Addition Chains
Noboru KUNIHIRO and Hirosuke YAMAMOTO
- Power exponentiation is an important operation in modern cryptography. This operation can be efficiently calculated using the concept of the addition chain. In this paper, two new systematic methods, a Run-length method and a Hybrid-method, are proposed to generate a short addition chain. The performance of these two methods are theoretically analyzed and it is shown that the Hybrid method is more efficient and practical than known methods. The proposed methods can reduce the addition chain length by 8%, in the best case, compared to the Window method.
- Key words: addition-subtraction chain, Hamming weight, extended window method, runlength method, hybrid method
- PDF (448 Kbytes) Copyright(c)2000 IEICE