О сложности задачи дискретного логарифмирования в интервале в группе с эффективным инвертированием

Задача дискретного логарифмирования в интервале заключается в поиске для заданной конечной группы $G=\langle P\rangle$ (с аддитивной записью операции) и заданных $P,Q\in G$, $N<|G|-1$ такого значения $n$, что $Q=nP$, $n\in\{-N/2,\dots,N/2\}$. Одним из наиболее эффективных методов решения данной задачи является алгоритм Годри–Шоста. В 2010 г. С. Гэлбрейт и Р. Рупраи представили усовершенствованную версию алгоритма для групп с эффективным инвертированием. Оценка средней трудоёмкости решения задачи составила $(1{,}36+\text o(1))\sqrt N$ групповых операций в $G$ при $N\to\infty$. В настоящей работе приводится новая модификация алгоритма Годри–Шоста для решения задачи дискретного логарифмирования в интервале в группе с эффективным инвертированием и получена оценка средней трудоёмкости, составляющая $(1+\varepsilon)\sqrt{\pi N/2}$ групповых операций в $G$.