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 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 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 x0, ..., xk−1 of an abelian group G and a vectorial addition chain of dimension k computing [n0, ..., nk−1] Output: The element x0n0...xk−1nr−1 for i = −k + 1 to 0 do yi → xi+k−1 for i = 1 to s do yi → yj × yr return ys == Addition sequence == An addition sequence for the set of integer S = {n0, ..., nr−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).