Window and Extended Window Methods for Addition Chain and Addition-Subtraction Chain

Noboru KUNIHIRO; Hirosuke YAMAMOTO

Window and Extended Window Methods for Addition Chain and Addition-Subtraction Chain

Noboru KUNIHIRO, Hirosuke YAMAMOTO

Full Text Views

0

Share
Cite this

Summary :

The addition chain (A-chain) and addition-subtraction chain (AS-chain) are efficient tools to calculate power M^e (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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E81-A No.1 pp.72-81

Publication Date: 1998/01/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)

Category

Cite this

Copy

Noboru KUNIHIRO, Hirosuke YAMAMOTO, "Window and Extended Window Methods for Addition Chain and Addition-Subtraction Chain" in IEICE TRANSACTIONS on Fundamentals, vol. E81-A, no. 1, pp. 72-81, January 1998, doi: .
Abstract: The addition chain (A-chain) and addition-subtraction chain (AS-chain) are efficient tools to calculate power M^e (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.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/e81-a_1_72/_p

Copy

@ARTICLE{e81-a_1_72,
author={Noboru KUNIHIRO, Hirosuke YAMAMOTO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Window and Extended Window Methods for Addition Chain and Addition-Subtraction Chain},
year={1998},
volume={E81-A},
number={1},
pages={72-81},
abstract={The addition chain (A-chain) and addition-subtraction chain (AS-chain) are efficient tools to calculate power M^e (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.},
keywords={},
doi={},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - Window and Extended Window Methods for Addition Chain and Addition-Subtraction Chain
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 72
EP - 81
AU - Noboru KUNIHIRO
AU - Hirosuke YAMAMOTO
PY - 1998
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E81-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 1998
AB - The addition chain (A-chain) and addition-subtraction chain (AS-chain) are efficient tools to calculate power M^e (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.
ER -