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

:{{math|1=v_−k+1 = [1,0,0,...0,0]}}

:{{math|1=v_−k+2 = [0,1,0,...0,0]}}

::: ⋮

::: ⋮

:{{math|1= v₀ = [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₀,...,n_k-1]

: w = (w₁,...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:{{cite conference

| last = de Rooij | first = Peter

| editor-last = Santis | editor-first = Alfredo De

| contribution = Efficient exponentiation using procomputation and vector addition chains

| doi = 10.1007/BFB0053453

| pages = 389–399

| publisher = Springer

| series = Lecture Notes in Computer Science

| title = Advances in Cryptology - EUROCRYPT '94, Workshop on the Theory and Application of Cryptographic Techniques, Perugia, Italy, May 9–12, 1994, Proceedings

| volume = 950

| year = 1994| isbn = 978-3-540-60176-0

}}

:Input: Elements x₀,...,x_k-1 of an abelian group G and a vectorial addition chain of dimension k computing [n₀,...,n_k-1]

:Output:The element x₀^n₀...x_k-1^n_r-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