This article is cited in 3 papers

Computational Methods in Discrete Mathematics

Improvement of the lower bound for the complexity of exponentiation

V. V. Kochergin, D. V. Kochergin

Lomonosov Moscow State University, Moscow, Russia

Abstract: Let $l(x^n)$ be the minimal number of multiplications sufficient for computing $x^n$. In the paper, we improve the lower bound of $l(x^n)$. We establish that for all $\varepsilon >0$ the fraction of the numbers $k$, $k\le n$, satisfying the relation
\begin{equation*} l(x^k)>\log_2n+\frac{\log_2n}{\log_2\log_2n}\left(1-(2+\varepsilon)\frac{\log_2\log_2\log_2n}{\log_2\log_2n}\right), \end{equation*}
tends to 1 as $n\to\infty$.

Keywords: addition chains, exponentiation, lower bounds of complexity.

UDC: 519.714.1

DOI: 10.17223/20710410/38/10

Bibliographic databases:

•