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 .