Vectorial addition chain

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 ≤ is together with a sequence w, such that

v-k+1 = [1,0,0,,...0,0]
v-k+2 = [0,1,0,,...0,0]
v0 = [0,0,0,,...0,1]
vi =vj+vr for all 1≤i≤s with -k+1≤j,r≤i-1
vs = [n0,...,nk-1]
w = (w1,, wi=(j,r).

For example, a vectorial addition chain for [22,18,3] is


Vectorial addition chains are well suited to perform multi-exponentiation:[citation needed]

Input: Elements x0,...,xk-1 of an abelian group G and a vectorial addition chain of dimension k computing [n0,...,nk-1]
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

Addition sequence[edit]

An addition sequence for the set of integer S ={n0, ...,nr-1} is an addition chain v that contains every element of S.

For example, an addition sequence computing




It's possible to find addition sequence from vectorial addition chains and vice versa, so they are in a sense dual.[1]

See also[edit]


  1. ^ Cohen, H., Frey, G. (editors): Handbook of elliptic and hyperelliptic curve cryptography. Discrete Math. Appl., Chapman & Hall/CRC (2006)