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   Vol.E81-A   No.1   pp.72-81
Publication Date: 1998/01/25
Online ISSN: 
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)>>
Buy this Article

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.