Efficient computation of addition chains

DOI10.5802/jtnb.104zbMath0812.11072MaRDI QIDQ1340674

Jean Berstel, François Bergeron, 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

zbMATH Keywords

complexity; minimal length; addition chain; \(cf\)-chains; contained fraction expansions; multiplication schemes; sub- optimal addition chains

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

11Y16: Number-theoretic algorithms; complexity

11Y65: Continued fraction calculations (number-theoretic aspects)

Related Items

Computing special powers in finite fields, On-line evaluation of powers using Euclid's algorithm, Hensel-lifting torsion points on Jacobians and Galois representations, A new strategy for generating shortest addition sequences, Mechanically proving termination using polynomial interpretations, Efficient computation of addition chains, Addition chains, vector chains, and efficient computation, Binary Addition Chain on EREW PRAM

Cites Work

• Unnamed Item
• Unnamed Item
• The Scholz-Brauer problem in addition chains
• 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\)
• Efficient computation of addition chains
• The Scholz-Brauer problem on addition chains
• On addition chains \(l(mn)\leq 1 (n)-b\) and lower bounds for c(r)
• Computing Sequences with Addition Chains
• On the Evaluation of Powers
• Addition chains using continued fractions
• The Computing Time of the Euclidean Algorithm