In this article, we will explore the topic of
Vectorial addition chain from different perspectives and approaches.
Vectorial addition chain has been a topic of interest for decades, and its relevance remains high today. During this tour, we will examine its origins, its impact on society and its evolution over time. Likewise, we will analyze the various opinions and positions that exist around
Vectorial addition chain, as well as the challenges and opportunities it presents. This article aims to provide a comprehensive and enriching view on
Vectorial addition chain, in order to provide the reader with a deeper and more complete understanding of this fascinating and influential topic.
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 =
- v−k+2 =
- ⋮
- ⋮
- v0 =
- vi =vj+vr for all 1≤i≤s with -k+1≤j, r≤i-1
- vs =
- w = (w1,...ws), wi=(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:[1]
- Input: Elements x0,...,xk-1 of an abelian group G and a vectorial addition chain of dimension k computing
- 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's possible to find addition sequence from vectorial addition chains and vice versa, so they are in a sense dual.[2]
See also
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)