On the construction of short addition-subtraction chains and their applications

Abstract

The problem of computing $x^n$ efficiently, such that $x$ and $n$ are known to be very interesting, specially when $n$ is very large. In order to find efficient methods to solve this problem, addition chains have been much studied, and generalized to addition-subtraction chains. These various chainshave been useful in finding efficient 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.