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

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