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

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

Read more about Vectorial Addition Chain: Addition Sequence, See Also

Famous quotes containing the words addition and/or chain:

“The force of truth that a statement imparts, then, its prominence among the hordes of recorded observations that I may optionally apply to my own life, depends, in addition to the sense that it is argumentatively defensible, on the sense that someone like me, and someone I like, whose voice is audible and who is at least notionally in the same room with me, does or can possibly hold it to be compellingly true.”
—Nicholson Baker (b. 1957)

“To avoid tripping on the chain of the past, you have to pick it up and wind it about you.”
—Mason Cooley (b. 1927)