О сложности задачи дискретного логарифмирования в интервале в группе с эффективным инвертированиемстатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАК
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 18 марта 2016 г.
Аннотация:Задача дискретного логарифмирования в интервале заключается в поиске для заданной конечной группы 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+ε)πN/2−−−−−√ групповых операций в G.