Vectorial addition chain

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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₀,...,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:^[1]

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

Addition sequence

An addition sequence for the set of integer S ={n₀, ..., 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.^[2]

References

^ de Rooij, Peter (1994). "Efficient exponentiation using procomputation and vector addition chains". In Santis, Alfredo De (ed.). Advances in Cryptology - EUROCRYPT '94, Workshop on the Theory and Application of Cryptographic Techniques, Perugia, Italy, May 9–12, 1994, Proceedings. Lecture Notes in Computer Science. Vol. 950. Springer. pp. 389–399. doi:10.1007/BFB0053453. ISBN 978-3-540-60176-0.
^ Cohen, H., Frey, G. (editors): Handbook of elliptic and hyperelliptic curve cryptography. Discrete Math. Appl., Chapman & Hall/CRC (2006)

[1] Rooij, Peter (1994). "Efficient exponentiation using procomputation and vector addition chains". In Santis, Alfredo De (ed.). Advances in Cryptology - EUROCRYPT '94, Workshop on the Theory and Application of Cryptographic Techniques, Perugia, Italy, May 9–12, 1994, Proceedings. Lecture Notes in Computer Science. Vol. 950. Springer. pp. 389–399. doi:10.1007/BFB0053453. ISBN 978-3-540-60176-0.

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

[1]

[2]

Addition sequence

See also

References