|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Вычислительные методы в дискретной математике
О сложности задачи дискретного логарифмирования в интервале в группе с эффективным инвертированием
М. В. Николаев Московский государственный университет им. М. В. Ломоносова, г. Москва, Россия
Аннотация:
Задача дискретного логарифмирования в интервале заключается в поиске для заданной конечной группы $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$.
Ключевые слова:
задача дискретного логарифмирования в интервале, алгоритм Годри–Шоста.
Образец цитирования:
М. В. Николаев, “О сложности задачи дискретного логарифмирования в интервале в группе с эффективным инвертированием”, ПДМ, 2015, № 2(28), 97–102
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdm508 https://www.mathnet.ru/rus/pdm/y2015/i2/p97
|
Статистика просмотров: |
Страница аннотации: | 207 | PDF полного текста: | 63 | Список литературы: | 36 |
|