Cadena de adición vectorial

En matemáticas, para los números enteros positivos k y s , una cadena de adición vectorial es una secuencia V de vectores k -dimensionales de números enteros no negativos v _i para − k + 1 ≤ i ≤ s junto con una secuencia w , tal que

v _{− k +1} = [1,0,0,...0,0]

v _{− k +2} = [0,1,0,...0,0]

⋮

⋮

v ₀ = [0,0,0,,...0,1]

v _i = v _j + v _r para todo 1≤ i ≤ s con - k +1≤ j , r ≤ i -1

v _s = [ n ₀ ,..., n _{k -1} ]

w = ( w ₁ ,... w _s ), w _i = ( j, r ).

Por ejemplo, una cadena de adición vectorial para [22,18,3] es

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))

Las cadenas de adición vectorial son muy adecuadas para realizar exponenciaciones múltiples : ^[1]

Entrada : Elementos x ₀ ,..., x _{k -1} de un grupo abeliano G y una cadena de adición vectorial de dimensión k calculando [ n ₀ ,..., n _{k -1} ]

Salida : El elemento x ₀ ^{n ₀} ... x _{k -1} ^{n _{r -1}}

1. para i = -k +1 a 0 hacemos y _i → x _{i + k -1}
2. para i = 1 a s hacer y _i → y _j × y _r
3. volver y _s

Una secuencia de adición para el conjunto de enteros S ={ n ₀ , ..., n _{r -1} } es una cadena de adición v que contiene cada elemento de S .

Por ejemplo, una secuencia de adición calculada

{47.117.343.499}

es

(1,2,4,8,10,11,18,36, 47,55,91,109 , 117,226 , 343,434,489, 499 ) .

Es posible encontrar secuencias de adición a partir de cadenas de adición vectoriales y viceversa, por lo que en cierto sentido son duales. ^[2]

• Cadena de adición
• Exponenciación de cadena de adición
• Exponenciación por cuadrado
• Forma no adyacente