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 ''v''_''i'' for −''k'' + 1 ≤ ''i'' ≤ ''s'' together with a sequence ''w'',
such that
:
:
::: ⋮
::: ⋮
:

: ''v''_''i'' =''v''_''j''+''v''_''r'' for all 1≤''i''≤''s'' with -''k''+1≤''j'', ''r''≤''i''-1
: ''v''_''s'' = 'n''₀,...,''n''_''k''-1: ''w'' = (''w''₁,...''w''_''s''), ''w''_''i''=(''j,r'').

For example, a vectorial addition chain for 2,18,3is
:''V''=( ,0,0 ,1,0 ,0,1 ,1,0 ,2,0 ,4,0 ,4,0 0,8,0 1,9,0 1,9,1 2,18,2 2,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 ''x''₀,...,''x''_''k''-1 of an abelian group ''G'' and a vectorial addition chain of dimension ''k'' computing 'n''_''0'',...,''n''_''k''-1
:Output:The element ''x''₀^''n''₀...''x''_''k''-1^{''n''_''r''-1}
:# for ''i'' =''-k''+1 to 0 do ''y''_''i'' → ''x''_{''i''+''k''-1}
:# for ''i'' = 1 to ''s'' do ''y''_''i'' →''y''_''j''×''y''_''r''
:#return ''y''_''s''

Addition sequence

An addition sequence for the set of integer ''S'' = is an addition chain ''v'' that contains every element of ''S''.

For example, an addition sequence computing
:
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.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

{{reflist

Addition chains