International Association
for Cryptologic Research

Applying the pothole method on the factors of numbers of the form $2^n-1$, we prove that if $2^n-1$ has carries of degree at most $$\kappa(2^n-1)=\frac{1}{2(1+c)}\lfloor \frac{\log n}{\log 2}\rfloor-1$$ for $c>0$ fixed, then the inequality $$\iota(2^n-1)\leq n-1+(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^n-1$ with carries of degree $$\kappa(2^n-1):=(\frac{1}{1+f(n)})\lfloor \frac{\log n}{\log 2}\rfloor-1$$ with $f(n)=o(\log n)$ and $f(n)\longrightarrow \infty$ as $n\longrightarrow \infty$ for $n\geq 4$ then the inequality $$\iota(2^n-1)\leq n-1+(1+\frac{2}{1+f(n)})\lfloor\frac{\log n}{\log 2}\rfloor$$ holds.