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
- for i =-k+1 to 0 do yi xi+k-1
- for i = 1 to s do yi yj×yr
- return ys
Read more about Vectorial Addition Chain: Addition Sequence, See Also
Famous quotes containing the words addition and/or chain:
“As easy mayst thou fall
A drop of water in the breaking gulf,
And take unmingled thence that drop again,
Without addition or diminishing,
As take from me thyself and not me too.”
—William Shakespeare (15641616)
“From Natures chain whatever link you strike,
Tenth or ten thousandth, breaks the chain alike.”
—Alexander Pope (16881744)