Аннотация:
Для величины $l(x^n)$ – минимального числа операций умножения, достаточного для вычисления по переменной $x$ степени $x^n$ – уточнена нижняя оценка. Установлено, что для любого $\varepsilon >0$ доля чисел $k$, не превосходящих $n$ и удовлетворяющих условию
\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*}
стремится к 1 при $n\to\infty$.
Ключевые слова:аддитивные цепочки, возведение в степень, нижние оценки сложности.