Paper 2023/051

On the Scholz conjecture on addition chains

Theophilus Agama, African Institute for Mathematical Sciences
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)
PDF
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
Creative Commons Attribution-ShareAlike
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.