Paper 2023/051
On the Scholz conjecture on addition chains
Abstract
Applying the pothole method on the factors of numbers of the form $2^n-1$, we prove the stronger inequality $$\iota(2^n-1)\leq n+1-\sum \limits_{j=1}^{\lfloor \frac{\log n}{\log 2}\rfloor}\xi(n,j)+3\lfloor\frac{\log n}{\log 2}\rfloor$$ for all $n\in \mathbb{N}$ with $n\geq 64$ for $0\leq \xi(n,j)<1$, where $\iota(\cdot)$ denotes the length of the shortest addition chain producing $\cdot$. This inequality is stronger than $$\iota(r)<\frac{\log r}{\log 2}(1+\frac{1}{\log \log r}+\frac{2\log 2}{(\log r)^{1-\log 2}})$$ in the case $r=2^n-1$ but slightly weaker than the conjectured inequality $$\iota(2^n-1)\leq n-1+\iota(n).$$
Metadata
- Available format(s)
- Category
- Applications
- Publication info
- Preprint.
- Keywords
- sub-addition chaindeterminersregulatorslengthgeneratorspartitioncomplete
- Contact author(s)
- theophilus @ aims edu gh
- History
- 2023-07-08: revised
- 2023-01-16: received
- See all versions
- Short URL
- https://ia.cr/2023/051
- License
-
CC BY-SA
BibTeX
@misc{cryptoeprint:2023/051, author = {Theophilus Agama}, title = {On the Scholz conjecture on addition chains}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/051}, year = {2023}, url = {https://eprint.iacr.org/2023/051} }