In mathematics, for positive integers "k" and "s", a vectorial addition chain is a sequence "V" of "k"-dimensional vectors of nonnegative integers "v""i" for −"k" + 1 ≤ "i" ≤ "s" together with a sequence "w",
such that
"v"−"k"+1 = [1,0,0...0,0]
"v"−"k"+2 = [0,1,0...0,0]
 ⋮
"v"0 = [0,0,0...0,1]
 "v""i" ="v""j"+"v""r" for all 1≤"i"≤"s" with -"k"+1≤"j", "r"≤"i"-1
 "v""s" = ["n"0...,"n""k"-1]
 "w" = ("w"1..."w""s"), "w""i"=("j,r").
For example, a vectorial addition chain for [22,18,3] is 
"V"=([1,0,0],[0,1,0],[0,0,1],[1,1,0],[2,2,0],[4,4,0],[5,4,0],[10,8,0],[11,9,0],[11,9,1],[22,18,2],[22,18,3])
"w"=((-2,-1),(1,1),(2,2),(-2,3),(4,4),(1,5),(0,6),(7,7),(0,8))
Vectorial addition chains are well suited to perform multi-exponentiation:
Input: Elements "x"0...,"x""k"-1 of an abelian group "G" and a vectorial addition chain of dimension "k" computing ["n""0"...,"n""k"-1] 
Output:The element "x"0"n"0..."x""k"-1"n""r"-1
# for "i" ="-k"+1 to 0 do "y""i" → "x""i"+"k"-1
# for "i" = 1 to "s" do "y""i" →"y""j"×"y""r" 
#return "y""s"
Addition sequence.
An addition sequence for the set of integer "S" ={"n"0, ..., "n""r"-1} is an addition chain "v" that contains every element of "S".
For example, an addition sequence computing 
{47,117,343,499} 
is
(1,2,4,8,10,11,18,36,47,55,91,109,117,226,343,434,489,499).
It's possible to find addition sequence from vectorial addition chains and vice versa, so they are in a sense dual.
References.
 ;templatestyles src="Reflist/styles.css" / ;