### 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^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.

Available format(s)
Category
Applications
Publication info
Preprint.
Keywords
Carriesdegrees
Contact author(s)
thaga1 @ ulaval ca
History
2024-07-29: approved
See all versions
Short URL
https://ia.cr/2024/1199

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}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.