Paper 2023/1959
On the notion of carries of numbers $2^n1$ and Scholz conjecture
Abstract
Applying the pothole method on the factors of numbers of the form $2^n1$, we prove that if $2^n1$ has carries of degree at most $$\kappa(2^n1)=\frac{1}{2(1+c)}\lfloor \frac{\log n}{\log 2}\rfloor1$$ for $c>0$ fixed, then the inequality $$\iota(2^n1)\leq n1+(1+\frac{1}{1+c})\lfloor\frac{\log n}{\log 2}\rfloor$$ holds for all $n\in \mathbb{N}$ with $n\geq 4$, where $\iota(\cdot)$ denotes the length of the shortest addition chain producing $\cdot$. In general, we show that all numbers of the form $2^n1$ with carries of degree $$\kappa(2^n1):=(\frac{1}{1+f(n)})\lfloor \frac{\log n}{\log 2}\rfloor1$$ with $f(n)=o(\log n)$ and $f(n)\longrightarrow \infty$ as $n\longrightarrow \infty$ for $n\geq 4$ then the inequality $$\iota(2^n1)\leq n1+(1+\frac{2}{1+f(n)})\lfloor\frac{\log n}{\log 2}\rfloor$$ holds.
Note: This paper is quite technical and it uses the newly introduced notion of carries to obtain improved upper bounds for the length of the shortest addition chains producing numbers of the form $2^n1$.
Metadata
 Available format(s)
 Category
 Applications
 Publication info
 Preprint.
 Keywords
 length
 Contact author(s)
 thaga1 @ ulaval ca
 History
 20231231: approved
 20231225: received
 See all versions
 Short URL
 https://ia.cr/2023/1959
 License

CC BYSA
BibTeX
@misc{cryptoeprint:2023/1959, author = {Theophilus Agama}, title = {On the notion of carries of numbers $2^n1$ and Scholz conjecture}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/1959}, year = {2023}, url = {https://eprint.iacr.org/2023/1959} }