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 vi 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],
- ⋮
- ⋮
- v0 = [0, 0, 0, ..., 0, 1],
- 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:[1]
- 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
[edit]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.[2]
See also
[edit]References
[edit]- ^ 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).