On addition-subtraction chains of numbers with low Hamming weight
Dustin Moody, Amadou Tall · Notes on Number Theory and Discrete Mathematics · 2019
An addition chain is a sequence of integers such that every element in the sequence is the sum of two previous elements.They have been much studied, and generalized to additionsubtraction chains, Lucas chains, and Lucas addition-subtraction chains.These various chains have been useful in finding efficient exponentiation algorithms in groups.As a consequence, finding chains of minimal length is critical.The main objective of this paper is to extend results known for addition chains to addition-subtraction chains with Lucas addition-subraction as a tool to construct such minimal chains.Specifically, if we let ℓ -(n) stand for the minimal length of all the Lucas addition-subtraction chains for n, we prove |ℓ -(2n) -ℓ -(n)| ≤ 1 for all integers n of Hamming weight ≤ 4. Thus, to find a minimal addition-subtraction chains for low Hamming weight integers, it suffices to only consider odd integers.