Efficient Generation of Minimal Length Addition Chains

Abstract

An addition chain for a positive integer n is a set 1 = a0 a1 ar=n of integers such that for each $i\ge 1$, $a_i=a_j+a_k$ for some $k\le j n. Particular attention is paid to various pruning techniques that cut down the search time for such chains. Certain of these techniques are influenced by the multiplicative structure of n. Later sections of the paper present some results that have been uncovered by searching for minimal length addition chains.