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
v−k+1 = [1, 0, 0, ..., 0, 0],
v−k+2 = [0, 1, 0, ..., 0, 0],
⋮
⋮
v0 = [0, 0, 0, ..., 0, 1],
vi = vj + vr for all 1 ≤ i ≤ s with −k + 1 ≤ j, r ≤ i − 1,
vs = [n0, ..., nk−1],
w = (w1, ..., ws), wi = (j, r).
For example, a vectorial addition chain for [22, 18, 3] is