Exploring Addition-Subtraction Chains

In this thesis, we will look into how can we generate addition-subtraction chains using generalized continued fraction. The algorithm that was proposed by Tall et all in 2013 and it is an extension of an algorithm for generating addition chains using continued fraction. The algorithm proposed uses generalized continued fraction, however, it does not show a method on generating a generalized continued fraction or any other heuristics. In this thesis we propose some heuristics that can be applied in generating generalized continued fraction. In chapter 1, we give an overview of exponentiation algorithms that can be used to generate addition-subtraction chains and some theoritical results. In chapter 2, we will look into known algorithms that attempt in generating short addition chains. In chapter 3, we will look into addition-subtraction chains and present our contribution, followed by a discussion on future work and conclusion.