A Note on Addition Chains
Maurice Mignotte, Amadou Tall · 2011
Addition chains give a very easy way of computing x n knowing x and n. The fact of having a minimal addition chain for an integer n gives the least number of multiplications needed to compute x n .I n this paper, we will present the binary method which is optimal for any integer of Hamming weight 1 or 2. We will show that if n has k digits in its binary expansion and the minimal length of all addition chains for n is k +1, then n has 2 as Hamming weight and we can then deduce that there exists a minimal addition chain obtained by the binary method for n. Finally, we will show that there are exactly 4 kinds of addition chains possible for those kinds of integers The binary method is also optimal for integers of Hamming weigh 3 but we will show that the converse is false in this case.