Бэби-шаг, гигантский шаг

В теории групп , разделе математики, «гигантский шаг ребенка» — это «встреча посередине» алгоритм для вычисления дискретного логарифма или порядка элемента в конечной абелевой группе, автор Дэниел Шэнкс . Проблема дискретного журнала имеет фундаментальное значение для области криптографии с открытым ключом .

Многие из наиболее часто используемых систем криптографии основаны на предположении, что дискретный журнал чрезвычайно сложно вычислить; чем сложнее, тем большую безопасность обеспечивает передача данных. Один из способов повысить сложность проблемы дискретного журнала — построить криптосистему на основе более крупной группы.

Теория

Алгоритм основан на компромиссе пространства и времени . Это довольно простая модификация пробного умножения, наивного метода нахождения дискретных логарифмов.

Учитывая циклическую группу $G$ порядка $n$, генератор $\alpha$ группы и элемента группы $\beta$, проблема в том, чтобы найти целое число $x$ такой, что

$\alpha ^{x}=\beta \,.$

Алгоритм «маленький шаг — гигантский шаг» основан на переписывании $x$:

$x=im+j$

$m=\left\lceil {\sqrt {n}}\right\rceil$

$0\leq i<m$

$0\leq j<m$

Таким образом, мы имеем:

$\alpha ^{x}=\beta \,$

$\alpha ^{im+j}=\beta \,$

$\alpha ^{j}=\beta \left(\alpha ^{-m}\right)^{i}\,$

Алгоритм предварительно вычисляет $\alpha ^{j}$ для нескольких значений $j$. Затем он исправляет $m$ и пробует значения $i$ в правой части приведенного выше сравнения, в порядке пробного умножения. Он проверяет, выполняется ли сравнение для любого значения $j$, используя заранее вычисленные значения $\alpha ^{j}$.

Алгоритм

Входные данные : циклическая группа G порядка n , имеющая генератор α и элемент β .

Выход : значение x, удовлетворяющее $\alpha ^{x}=\beta$.

1. м ← Потолок( √ n )
2. Для всех j , где 0 ≤ j < m :
   1. Вычислить α ^дж и сохраним пару ( j , α ^дж ) в таблице. (См. § На практике )
3. Вычислить α ^{− м} .
4. в ← б . (установить γ = β )
5. Для всех i , где 0 ≤ i < m :
   1. Проверьте, является ли γ вторым компонентом ( α ^дж ) любой пары в таблице.
   2. Если да, верните im + j .
   3. Если нет, c ← c • a ^{− м} .

На практике

Лучший способ ускорить алгоритм «маленький шаг — гигантский шаг» — использовать эффективную схему поиска в таблице. Лучшее в этом случае — хеш-таблица . Хеширование выполняется для второго компонента, и для выполнения проверки на шаге 1 основного цикла хешируется γ и проверяется полученный адрес памяти. Поскольку хеш-таблицы могут извлекать и добавлять элементы в $O(1)$ время (постоянное время), это не замедляет общий алгоритм гигантского шага ребенка.

Пространственная сложность алгоритма равна $O({\sqrt {n}})$, а временная сложность алгоритма равна $O({\sqrt {n}})$. Это время работы лучше, чем $O(n)$ время выполнения наивного грубого расчета.

Алгоритм гигантского шага Baby-step может быть использован перехватчиком для получения закрытого ключа, сгенерированного при обмене ключами Диффи-Хеллмана , когда модуль представляет собой простое число, которое не слишком велико. Если модуль не является простым, алгоритм Полига – Хеллмана имеет меньшую алгоритмическую сложность и потенциально решает ту же проблему.

Примечания

• Алгоритм «маленький шаг — гигантский шаг» — это универсальный алгоритм. Это работает для любой конечной циклической группы.
• Нет необходимости знать точный порядок группы G. заранее Алгоритм по-прежнему работает, если n — это просто верхняя граница порядка группы.
• Обычно алгоритм «маленького шага» и «гигантского шага» используется для групп, порядок которых является простым. Если порядок группы составной, то алгоритм Полига – Хеллмана более эффективен.
• Алгоритм требует O ( m ) памяти. Можно использовать меньше памяти, выбрав меньшее m на первом этапе алгоритма. Это увеличивает время работы, которое тогда равно O ( n / m ). В качестве альтернативы можно использовать ро-алгоритм Полларда для логарифмов , который имеет примерно то же время работы, что и алгоритм гигантского шага ребенка, но требует лишь небольшого объема памяти.
• Хотя авторство этого алгоритма принадлежит Дэниелу Шэнксу, опубликовавшему в 1971 году статью, в которой он впервые появился, статья Нечаева 1994 года утверждает, что он был известен Гельфонду в 1962 году.
• Существуют оптимизированные версии исходного алгоритма, например, с использованием усеченных справочных таблиц без коллизий или карты отрицания и одновременную модульную инверсию Монтгомери, как предложено в .

Дальнейшее чтение

• Х. Коэн , Курс вычислительной алгебраической теории чисел, Springer, 1996.
• Д. Шэнкс , Число классов, теория факторизации и родов. В Proc. Симп. Чистая математика. 20, страницы 415–440. AMS, Провиденс, Род-Айленд, 1971 г.
• А. Штейн и Э. Теске, Оптимизированные методы детского шага и гигантского шага, Журнал Математического общества Рамануджана 20 (2005), вып. 1, 1–32.
• А.В. Сазерленд , Порядковые вычисления в генерических группах , Кандидатская диссертация, Массачусетский технологический институт, 2007.
• Д.С. Терр, Модификация алгоритма «гигантский шаг» Шанкса, Mathematics of Computation 69 (2000), 767–773. два : 10.1090/S0025-5718-99-01141-2

Внешние ссылки

• Детский шаг-Гигантский шаг – пример исходного кода C