<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

Publié en ligne: 07 mars 2023

Pages: 131 - 144

Reçu: 03 déc. 2022

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

Mots clés
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

Publié en ligne: 07 mars 2023

Pages: 131 - 144

Reçu: 03 déc. 2022

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

Mots clésaddition-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.

Mots clés
addition-subtraction chains, non-adjacent form, strategy, minimal length of chain, generalized continued fractions, Euclidean algorithm