Vectorial addition chain (original) (raw)
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-1vs = [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))
| Property | Value |
|---|---|
| dbo:abstract | 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-1vs = [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: 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 1. * for i =-k+1 to 0 do yi → xi+k-1 2. * for i = 1 to s do yi →yj×yr 3. * return ys (en) |
| dbo:wikiPageID | 21139664 (xsd:integer) |
| dbo:wikiPageLength | 2519 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1024809967 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Non-adjacent_form dbr:Addition-chain_exponentiation dbr:Addition_chain dbc:Addition_chains dbr:Exponentiation dbr:Exponentiation_by_squaring dbr:Abelian_group |
| dbp:wikiPageUsesTemplate | dbt:Citation_needed dbt:Math dbt:Reflist |
| dct:subject | dbc:Addition_chains |
| rdf:type | yago:Abstraction100002137 yago:Company108058098 yago:Group100031264 yago:Institution108053576 yago:Organization108008335 yago:YagoLegalActor yago:YagoLegalActorGeo yago:YagoPermanentlyLocatedEntity yago:SocialGroup107950920 yago:WikicatAdditionChains |
| rdfs:comment | 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-1vs = [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)) (en) |
| rdfs:label | Vectorial addition chain (en) |
| owl:sameAs | freebase:Vectorial addition chain yago-res:Vectorial addition chain wikidata:Vectorial addition chain https://global.dbpedia.org/id/4xMKM |
| prov:wasDerivedFrom | wikipedia-en:Vectorial_addition_chain?oldid=1024809967&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Vectorial_addition_chain |
| is dbo:wikiPageWikiLink of | dbr:Addition-subtraction_chain dbr:Addition_chain dbr:Exponentiation_by_squaring |
| is foaf:primaryTopic of | wikipedia-en:Vectorial_addition_chain |