Vectorial addition chain


In mathematics, for positive integers k and s, a vectorial addition chain is a sequence V of k-dimensional vectors of nonnegative integers vi for −k + 1 ≤ i ≤ s together with a sequence w,
such that
For example, a vectorial addition chain for is
Vectorial addition chains are well suited to perform multi-exponentiation:

Addition sequence

An addition sequence for the set of integer S = is an addition chain v that contains every element of S.
For example, an addition sequence computing
is
It's possible to find addition sequence from vectorial addition chains and vice versa, so they are in a sense dual.