In mathematics, for positive integers k and s, a vectorial addition chain is a sequence V of k-dimensional vectors vi of nonnegative integers for −k + 1 ≤ i ≤ s together with a sequence w, such that , , ⋮ ⋮ ,
vi = vj + vr for all 1 ≤ i ≤ s with −k + 1 ≤ j, r ≤ i − 1, vs = [n0, ..., nk−1], w = (w1, ..., ws), wi = (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 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 for i = −k + 1 to 0 do yi → xi+k−1 for i = 1 to s do yi → yj × yr return ys
Addition sequence 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 {47, 117, 343, 499} is (1, 2, 4, 8, 10, 11, 18, 36, 47, 55, 91, 109, 117, 226, 343, 434, 489, 499).
It is possible to find addition sequence from vectorial addition chains and conversely, so they are in a sense dual.Cohen, H., Frey, G. (editors): Handbook of elliptic and hyperelliptic curve cryptography. Discrete Math. Appl., Chapman & Hall/CRC (2006).
See also Addition chain Addition-chain exponentiation Exponentiation by squaring Non-adjacent form
References