Аннотация:
Исследуются в асимптотической постановке различные обобщения классической задачи о наискорейшем возведении в степень, известной также как задача об аддитивных цепочках. Для двух наиболее известных обобщений — для задачи Ричарда Беллмана о сложности (наименьшем числе операций умножения) вычисления (исходя только из переменных) нормированного одночлена от m переменных и для задачи Дональда Кнута о сложности совместного вычисления системы из m степеней одной переменной — при слабых ограничениях предъявлено асимптотически точное решение. Кроме того, дан краткий обзор результатов по сложности вычислений, касающихся следующих трёх задач: вычисление системы из p нормированных одночленов от q переменных; аддитивные вычисления систем из p линейных форм от q переменных; вычисление системы из p элементов свободной абелевой группы с q порождающими.
Ключевые слова:
аддитивные цепочки, векторные аддитивные цепочки, цепочки из сложений и вычитаний, цепочки слов, вычисление одночленов, вычисление степеней, задача Беллмана, задача Кнута.
Образец цитирования:
В. В. Кочергин, “О задачах Беллмана и Кнута и их обобщениях”, Фундамент. и прикл. матем., 20:6 (2015), 159–188; J. Math. Sci., 233:1 (2018), 103–124
\RBibitem{Koc15}
\by В.~В.~Кочергин
\paper О задачах Беллмана и Кнута и их обобщениях
\jour Фундамент. и прикл. матем.
\yr 2015
\vol 20
\issue 6
\pages 159--188
\mathnet{http://mi.mathnet.ru/fpm1692}
\transl
\jour J. Math. Sci.
\yr 2018
\vol 233
\issue 1
\pages 103--124
\crossref{https://doi.org/10.1007/s10958-018-3928-4}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/fpm1692
https://www.mathnet.ru/rus/fpm/v20/i6/p159
Эта публикация цитируется в следующих 7 статьяx:
Utkarsh Tiwari, Satyanarayana Vollala, N. Ramasbramanian, B. Shameedha Begum, “Right-to-Left Multi-Core Multi-Modular Exponentiation for Authentication Protocols”, IEEE Network, 39:1 (2025), 205
В. В. Кочергин, “О сложности вычисления систем элементов конечных абелевых групп”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2023, № 4, 22–29; V. V. Kochergin, “On the computation complexity of the systems of finite Abelian group elements”, Moscow University Mathematics Bulletin, 78:4 (2023), 179–187
Vidal Attias, Luigi Vigneri, Vassil Dimitrov, “Rethinking modular multi-exponentiation in real-world applications”, J Cryptogr Eng, 13:1 (2023), 57
В. В. Кочергин, “Сравнение сложности вычисления одночленов и элементов конечных абелевых групп”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2022, № 3, 6–11; V. V. Kochergin, “Comparing the computational complexity of monomials and elements of finite Abelian groups”, Moscow University Mathematics Bulletin, 77:3 (2022), 113–119
С. А. Корнеев, “О сложности реализации системы мономов от двух переменных схемами композиции”, ПДМ, 2021, № 53, 103–119
С. А. Корнеев, “О поведении функции Шеннона сложности реализации систем мономов схемами композиции”, Интеллектуальные системы. Теория и приложения, 25:3 (2021), 173–188
В. В. Кочергин, “Простое доказательство верхней оценки сложности вычисления трех одночленов трeх переменных”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2019, № 2, 3–8; V. V. Kochergin, “A simple proof for the upper bound of the computational complexity of three monomials in three variables”, Moscow University Mathematics Bulletin, 74:2 (2019), 43–48
Цитирование в формате AMSBIB
Обратная связь: