Welcome to the resource topic for 2024/1199
Title:
On degrees of carry and Scholz’s conjecture
Authors: Theophilus Agama
Abstract:Exploiting the notion of carries, we obtain improved upper bounds for the length of the shortest addition chains \iota(2^n-1) producing 2^n-1. Most notably, we show that if 2^n-1 has carries of degree at most $$\kappa(2^n-1)=\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^n-1)\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.
ePrint: https://eprint.iacr.org/2024/1199
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .