Vectorial addition chain
In mathematics, for positive integers k and s, a vectorial addition chain is a sequence V of k-dimensional vectors vi of nonnegative integers 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 is possible to find addition sequence from vectorial addition chains and conversely, so they are in a sense dual.