For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Window and Extended Window Methods for Addition Chain and Addition-Subtraction Chain
Noboru KUNIHIRO Hirosuke YAMAMOTO
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1998/01/25
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
addition-subtraction chain, Tunstall code, canonical signed binary representation, window method,
Full Text: PDF(798.7KB)>>
The addition chain (A-chain) and addition-subtraction chain (AS-chain) are efficient tools to calculate power Me (or multiplication eM), where integere is fixed andM is variable. Since the optimization problem to find the shortest A (or AS)-chain is NP-hard, many algorithms to get a sub-optimal A (or AS)-chain in polynomial time are proposed. In this paper, a window method for the AS-chain and an extended window method for the A-chain and AS-chain are proposed and their performances are theoretically evaluated by applying the theory of the optimal variable-to-fixed length code, i. e. , Tunstall code, in data compression. It is shown by theory and simulation that the proposed algorithms are more efficient than other algorithms in practical cases in addition to the asymptotic case.