Paper 2024/1199
On degrees of carry and Scholz's conjecture
Abstract
Exploiting the notion of carries, we obtain improved upper bounds for the length of the shortest addition chains $\iota(2^n1)$ producing $2^n1$. Most notably, we show that if $2^n1$ has carries of degree at most $$\kappa(2^n1)=\frac{1}{2}(\iota(n)\lfloor \frac{\log n}{\log 2}\rfloor+\sum \limits_{j=1}^{\lfloor \frac{\log n}{\log 2}\rfloor}\{\frac{n}{2^j}\})$$ then the inequality $$\iota(2^n1)\leq n+1+\sum \limits_{j=1}^{\lfloor \frac{\log n}{\log 2}\rfloor}\bigg(\{\frac{n}{2^j}\}\xi(n,j)\bigg)+\iota(n)$$ holds for all $n\in \mathbb{N}$ with $n\geq 4$, where $\iota(\cdot)$ denotes the length of the shortest addition chain producing $\cdot$, $\{\cdot\}$ denotes the fractional part of $\cdot$ and where $\xi(n,1):=\{\frac{n}{2}\}$ with $\xi(n,2)=\{\frac{1}{2}\lfloor \frac{n}{2}\rfloor\}$ and so on.
Metadata
 Available format(s)
 Category
 Applications
 Publication info
 Preprint.
 Keywords
 Carriesdegrees
 Contact author(s)
 thaga1 @ ulaval ca
 History
 20240729: approved
 20240725: received
 See all versions
 Short URL
 https://ia.cr/2024/1199
 License

CC BY
BibTeX
@misc{cryptoeprint:2024/1199, author = {Theophilus Agama}, title = {On degrees of carry and Scholz's conjecture}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1199}, year = {2024}, url = {https://eprint.iacr.org/2024/1199} }