Efficient computation of addition chains

DOI10.5802/jtnb.104zbMath0812.11072OpenAlexW1994702909MaRDI 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

complexityminimal lengthaddition chain\(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)

Related Items (8)

Efficient computation of addition chains ⋮ Mechanically proving termination using polynomial interpretations ⋮ Computing special powers in finite fields ⋮ On-line evaluation of powers using Euclid's algorithm ⋮ A new strategy for generating shortest addition sequences ⋮ Addition chains, vector chains, and efficient computation ⋮ Hensel-lifting torsion points on Jacobians and Galois representations ⋮ 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

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