<abstract xmlns="http://www.w3.org/1999/xhtml">

<p>The problem of computing <italic>x<sup>n</sup></italic> effciently, such that <italic>x</italic> and <italic>n</italic> are known to be very interesting, specially when <italic>n</italic> is very large. In order to find effcient methods to solve this problem, addition chains have been much studied, and generalized to addition-subtraction chains. These various chains have been useful in finding effcient exponentiation algorithms. In this paper, we present a new method to recover all existing exponentiation algorithms. It will be applied to design a new fast exponentiation method.</p>
</abstract>

The problem of computing xn effciently, such that x and n are known to be very interesting, specially when n is very large. In order to find effcient methods to solve this problem, addition chains have been much studied, and generalized to addition-subtraction chains. These various chains have been useful in finding effcient exponentiation algorithms. In this paper, we present a new method to recover all existing exponentiation algorithms. It will be applied to design a new fast exponentiation method.

On the Construction of Short Addition-Subtraction Chains and their Applications

Tatra Mountains Mathematical Publications

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

{"article-title":"On the Construction of Short Addition-Subtraction Chains and their Applications"}

The problem of computing xn effciently, such that x and n are known to be very interesting, specially when n is very large. In order to find effcient methods...

On the Construction of Short Addition-Subtraction Chains and their Applications

Published Online: Mar 07, 2023

Page range: 131 - 144

Received: Dec 03, 2022

DOI: https://doi.org/10.2478/tmmp-2023-0010

Keywords
addition-subtraction chains, non-adjacent form, strategy, minimal length of chain, generalized continued fractions, Euclidean algorithm

© 2023 Mathematical Institute, Slovak Academy of Sciences

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

On the Construction of Short Addition-Subtraction Chains and their Applications

Published Online: Mar 07, 2023

Page range: 131 - 144

Received: Dec 03, 2022

DOI: https://doi.org/10.2478/tmmp-2023-0010

Keywordsaddition-subtraction chains, non-adjacent form, strategy, minimal length of chain, generalized continued fractions, Euclidean algorithm

© 2023 Mathematical Institute, Slovak Academy of Sciences

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Keywords
addition-subtraction chains, non-adjacent form, strategy, minimal length of chain, generalized continued fractions, Euclidean algorithm