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's possible to find addition sequence from vectorial addition chains and vice versa, 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.
- ^ Cohen, H., Frey, G. (editors): Handbook of elliptic and hyperelliptic curve cryptography. Discrete Math. Appl., Chapman & Hall/CRC (2006)