Vectorial addition chain

In mathematics, for positive integers k and s, a vectorial addition chain is a sequence V of k-dimensional vectors v_i of nonnegative integers for −k + 1 ≤ i ≤ s together with a sequence w, such that

,

,

: ⋮

: ⋮

,

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:

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}}

# 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₀, ..., 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.

See also

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

References