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)

    “The years seemed to stretch before her like the land: spring, summer, autumn, winter, spring; always the same patient fields, the patient little trees, the patient lives; always the same yearning; the same pulling at the chain—until the instinct to live had torn itself and bled and weakened for the last time, until the chain secured a dead woman, who might cautiously be released.”
    —Willa Cather (1873–1947)