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 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, 1],

v_i = v_j + v_r for all 1 ≤ i ≤ s with −k + 1 ≤ j, r ≤ i − 1,

v_s = [n₀, ..., n_k−1],

w = (w₁, ..., 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:^[1]

Input: Elements x₀, ..., x_k−1 of an abelian group G and a vectorial addition chain of dimension k computing [n₀, ..., n_k−1]

Output: The element x₀^n₀...x_k−1^n_r−1

1. for i = −k + 1 to 0 do y_i → x_i+k−1
2. for i = 1 to s do y_i → y_j × y_r
3. return y_s

Addition sequence

An addition sequence for the set of integer S = {n₀, ..., 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 is possible to find addition sequence from vectorial addition chains and conversely, so they are in a sense dual.^[2]

See also

• Addition chain
• Addition-chain exponentiation
• Exponentiation by squaring
• Non-adjacent form