О сложности задачи дискретного логарифмирования в интервале в группе с эффективным инвертированием | Прикладная дискретная математика. 2015. № 2 (28).

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