Misplaced Pages

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 =

v_−k+2 =

⋮

⋮

v₀ =

v_i =v_j+v_r for all 1≤i≤s with -k+1≤j, r≤i-1

v_s =

w = (w₁,...w_s), w_i=(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 x₀,...,x_k-1 of an abelian group G and a vectorial addition chain of dimension k computing

Output:The element x₀...x_k-1

1. for i =-k+1 to 0 do y_i → x_i+k-1
2. for i = 1 to s do y_i →y_j×y_r
3. 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.

See also

• Addition chain
• Addition-chain exponentiation
• Exponentiation by squaring
• Non-adjacent form

References

1. 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.
2. Cohen, H., Frey, G. (editors): Handbook of elliptic and hyperelliptic curve cryptography. Discrete Math. Appl., Chapman & Hall/CRC (2006)

• Addition chains