Shorter Addition-Subtraction Chain With Signed Composition Method
Mohamed MA, A Ahmad, Rajina R. Mohamed, Said MRM · International Journal of Engineering and Technology · 2017
Addition chain is considered as the solution to large number operation of scalar multiplication in elliptic curve cryptosystem.Recently, a decomposition method was introduced as a new technique to generate addition chain with minimal possible terms.The method which is based on prime power input form was shown to outclass previous methods under certain condition.An earlier study shows that this method can also be used with non-prime integer such that found in composition method.As a result of no extra cost for point negation on elliptic curve, subtraction operation can be included during the generation of the chain as we found in signed decomposition method.As an alternative, in this paper, we proposed a signed composition method.Using this method, we study the properties of the chain against those generated by prime power equivalent.The comparative result between signed composition method against signed decomposition method shows that by allowing a subtraction information into the chain, the resulting chains are nearly of equal length which is very different from the unsigned case, where original decomposition method is by far has outperformed the composition method.Keywords-addition chain, binary method, double and add, non-adjacent form, complementary recoding I. INTRODUCTION The term addition chain refers to the sequence of integers 1 = a 0 , a 1 , . . ., n starting from 1 and ending with n where only addition and doubling operations of two previous terms are allowed.The idea has been widely used to improved efficiency of huge number operation such that found in modern public key cryptography [1,2].The advent of elliptic curve cryptography (ECC) which allows negation of a point oncurve at no extra cost triggered the need to include subtraction operation during the construction of the so-called addition-subtraction chain.However, the problem of finding the optimal chain (or optimal sequence to be more precise) is unsolvable in areasonable time [3].Therefore, many heuristic methods [4,5,6,7] and metaheuristics [8, 9] methods were introduced, and each method works well only on some occasion.Recently, a new method called decomposition method (DM) [10] was introduced as another partial solution to the infamous addition chain problem.This method takes an input of a prime factor in the form of rules as an alternative representation for numbers.The method was shown to perform better than previous methods under certain condition.Shortly after, the same author also developed a method taking theinput of composite form namely the composition method (CM) [11] which takes an integer input in the form of rules.However, these two methods were targeting unsigned binary input, that is to improve the addition chain.For a signed binary input or to improve addition subtraction chain, a signed decomposition method (SDM) [12], as an advancement to DM was also introduced.This method seems to outperformed previous methods for some selected inputs.In this paper, we introduce a signed composition method (SCM).It mains objectives is to continue the work of composition method, that is to address the problem of addition-subtraction chain by allowing subtraction operation.SCM is compared mainly against SDM.For a given number range, the frequency of optimality is studied.We also study the properties of optimality as the number grows bigger.This paper is organized such a way that, Section 2 is dedicated to the introduction of the two different inputs forms.Section 3 shows the development of the idea of SCM.Section 4 suggests the algorithm for this new technique.Section 5 presents the analysis of the chain generated by SCM.Section 6 layouts the result to support our claim made earlier.Section 7 concludes the finding of this work.