Efficient computation of addition chains

DOI10.5802/JTNB.104MaRDI QIDQ1340674zbMATH OpenOpenAlexFDO

Authors F. Bergeron, Jean Berstel, Srečko Brlek

Publication date 15 May 1995

Published in Journal de Théorie des Nombres de Bordeaux (Search for Journal in Brave)

Full work available at URL http://www.numdam.org/item?id=JTNB_1994__6_1_21_0, http://www.numdam.org/item?id=JTNB_1994__6_1_21_0/, https://eudml.org/doc/229412, http://www.emis.de/journals/JTNB/1994-1/jtnb6-1.html

zbMATH Keywords

complexityaddition chainminimal length\(cf\)-chainscontained fraction expansionsmultiplication schemessub- optimal addition chains

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) Continued fraction calculations (number-theoretic aspects) (11Y65)

Recommendations

• Minimizing sums of addition chains
• Efficient Generation of Minimal Length Addition Chains
• Efficient generation of shortest addition-multiplication chains
• Effect of Improved Multiplication Efficiency on Exponentiation Algorithms Derived from Addition Chains
• A new strategy for generating shortest addition sequences
• Star reduction among minimal length addition chains
• Improved generation of minimal addition chains
• Addition chains, vector chains, and efficient computation
• scientific article; zbMATH DE number 1946632
• Rule based representation of integer for a new addition chain method

Cites work

• scientific article; zbMATH DE number 3808949 (Why is no real title available?)
• scientific article; zbMATH DE number 3750146 (Why is no real title available?)
• A lower bound for the length of addition chains
• Addition chains and solutions of \(\ell(2n)=\ell(n)\) and \(\ell(2^n-1)= n+\ell(n)-1\)
• Addition chains using continued fractions
• Computing Sequences with Addition Chains
• Efficient computation of addition chains
• On addition chains \(l(mn)\leq 1 (n)-b\) and lower bounds for c(r)
• On the Evaluation of Powers
• The Computing Time of the Euclidean Algorithm
• The Scholz-Brauer problem in addition chains
• The Scholz-Brauer problem on addition chains

Cited in

(17)

• A new strategy for generating shortest addition sequences
• Calculating optimal addition chains
• Mechanically proving termination using polynomial interpretations
• Addition chains, vector chains, and efficient computation
• Improved generation of minimal addition chains
• Addition chains using continued fractions
• Binary addition chain on EREW PRAM
• Effect of Improved Multiplication Efficiency on Exponentiation Algorithms Derived from Addition Chains
• Addition chains meet postage stamps: reducing the number of multiplications
• Accelerated shift-and-add algorithms
• On a generalization of addition chains: addition-multiplication chains
• Efficient computation of addition chains
• Hensel-lifting torsion points on Jacobians and Galois representations
• scientific article; zbMATH DE number 7235119 (Why is no real title available?)
• Computing When Multiplications Cost Nothing
• On-line evaluation of powers using Euclid's algorithm
• Computing special powers in finite fields

This page was built for publication: Efficient computation of addition chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1340674)