Calculating optimal addition chains
An addition chain for a natural number \(n\) is a sequence \(1=a_0 < a_1 < \cdots < a_r =n\) of integers such that for each \(0 < i \leq r\), \(a_i = a_j+a_k\) for some \(0\leq k \leq j <i\). The minimal length of an addition chain for \(n\) is denoted by \(\ell(n)\) and such a chain of length \(\ell(n)\) is called \textit{optimal}. The author presents a new algorithm for calculating optimal chains. When used for a single value \(n\) this algorithm is slower than the best known present ones but it is faster when used to calculate a range of optimal addition chains. Using this new algorithm the author computed the values of \(\ell(n)\) for \(n\leq 2^{32}\), this gives a disproof of the conjecture \(\ell(2n)\geq \ell(n)\). Moreover, exact equality in the Scholz-Brauer conjecture \(\ell(2^n-1)=\ell(n)+n-1\) has been confirmed for many new values.
- A Lower Bound for the Scholz-Brauer Problem
- A Note on the Scholz-Brauer Problem in Addition Chains
- A public key cryptosystem and a signature scheme based on discrete logarithms
- A Survey of Fast Exponentiation Methods
- Addition chains and solutions of \(\ell(2n)=\ell(n)\) and \(\ell(2^n-1)= n+\ell(n)-1\)
- Efficient Generation of Minimal Length Addition Chains
- scientific article; zbMATH DE number 3121508 (Why is no real title available?)
- scientific article; zbMATH DE number 683826 (Why is no real title available?)
- scientific article; zbMATH DE number 697837 (Why is no real title available?)
- scientific article; zbMATH DE number 2024859 (Why is no real title available?)
- Integers with a small number of minimal addition chains
- On addition chains
- Some Properties of Nonstar Steps in Addition Chains and New Cases Where the Scholz Conjecture Is True
- The Scholz-Brauer problem on addition chains
- Some results on addition/subtraction chains
- Internal structure of addition chains: well-ordering
- Chain addition cycles
- Addition chains, vector chains, and efficient computation
- Koblitz curves over quadratic fields
- scientific article; zbMATH DE number 1665443 (Why is no real title available?)
- A Conjecture in Addition Chains Related to Scholz's Conjecture
- scientific article; zbMATH DE number 7235119 (Why is no real title available?)
- Minimizing sums of addition chains
- Computing When Multiplications Cost Nothing
- scientific article; zbMATH DE number 1946632 (Why is no real title available?)
- Addition chains using continued fractions
- Lower Bounds for Lucas Chains
- On-line evaluation of powers using Euclid's algorithm
- IMPROVEMENT OF THE LOWER BOUND FOR THE COMPLEXITY OF EXPONENTIATION
- Efficient generation of shortest addition-multiplication chains
- Addition chains meet postage stamps: reducing the number of multiplications
- The Scholz conjecture on addition chain is true for infinitely many integers with \ell(2n)= \ell(n)
- Star reduction among minimal length addition chains
- Searching for differential addition chains
- On the minimal length of addition chains
- Polyploidy arithmetic
- Low-cost addition-subtraction sequences for the final exponentiation in pairings
- Improved generation of minimal addition chains
This page was built for publication: Calculating optimal addition chains
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q644848)
