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 =

v_-k+2 =

.

.

v₀ =

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

v_s =

w = (w₁,...w_s), w_i=(j,r).

For example, a vectorial addition chain for is

V=(,,,,,,,,,,,)

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

Output:The element x₀n₀...x_k-1n_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