title: Vectorial addition chain
text: # 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 $v_i$ for −k + 1 ≤ i ≤ s together with a sequence w, such that
  
      $v_{−k+1}$ = [1,0,0,...0,0]
      $v_{−k+2}$ = [0,1,0,...0,0]
      $v_0$ = [0,0,0,,...0,1]
      $v_i$ $=v_j+v_r$ for all 1≤i≤s with -k+1≤j, r≤i-1
      $v_s$ = $[n_0,...,n_{k-1}]$
      w = $(w_1,...w_s),$ $w_i=(j,r).$
  
  For example, a vectorial addition chain for [22,18,3] is
  
      V=([1,0,0],[0,1,0],[0,0,1],[1,1,0],[2,2,0],[4,4,0],[5,4,0],[10,8,0],[11,9,0],[11,9,1],[22,18,2],[22,18,3])
      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 $x_0,...,x_{k-1}$ of an abelian group G and a vectorial addition chain of dimension k computing $[n_0,...,n_{k-1}]$
      Output:The element $x_0^{n0}...x_{k-1}^{nr-1}$
     * for i =-k+1 to 0 do $y_i$ → $x_{i+k-1}$
  
     * for i = 1 to s do $y_i$ $→y_j×y_r$
  
     * return $y_s$
  
  ## Addition sequence
  
  An addition sequence for the set of integer S $={n_0,$ ..., $n_{r-1}}$ is an addition chain v that contains every element of S.
  
  For example, an addition sequence computing
  
      {47,117,343,499}
  
  is
  
      (1,2,4,8,10,11,18,36,47,55,91,109,117,226,343,434,489,499).
  
  It's possible to find addition sequence from vectorial addition chains and vice versa, so they are in a sense dual.
  
  