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 vi 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-<a href="/facts/Exponentiation/pac6QY2g">exponentiation</a>:

Input: Elements x0,...,xk-1 of an <a href="/facts/Abelian_group/FfWwmx4R">abelian group</a> G and a vectorial addition chain of dimension k computing [n0,...,nk-1]
Output:The element x0n0...xk-1nr-1
<ol><li>for i =-k+1 to 0 do yi → xi+k-1</li>
<li>for i = 1 to s do yi →yj×yr</li>
<li>return ys</li></ol>

Vectorial addition chain open-in-new

Vectorial addition chain