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)

    “By this unprincipled facility of changing the state as often, and as much, and in as many ways as there are floating fancies or fashions, the whole chain and continuity of the commonwealth would be broken. No one generation could link with the other. Men would become little better than the flies of a summer.”
    —Edmund Burke (1729–1797)