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 =
v-k+2 =
.
.
v0 =
vi =vj+vr for all 1≤i≤s with -k+1≤j,r≤i-1
vs =
w = (w1,...ws), wi=(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 x0,...,xk-1 of an abelian group G and a vectorial addition chain of dimension k computing
Output:The element x0n0...xk-1nr-1
  1. for i =-k+1 to 0 do yi xi+k-1
  2. for i = 1 to s do yi yj×yr
  3. return ys

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

Famous quotes containing the words addition and/or chain:

    “Napoleon wanted to turn Paris into Rome under the Caesars, only with louder music and more marble. And it was done. His architects gave him the Arc de Triomphe and the Madeleine. His nephew Napoleon III wanted to turn Paris into Rome with Versailles piled on top, and it was done. His architects gave him the Paris Opera, an addition to the Louvre, and miles of new boulevards.”
    —Tom Wolfe (b. 1931)

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