Бэби-степ гигант-шаг

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

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

• 1 Теория
• 2 Алгоритм
  • 2.1 Алгоритм C ++ (C ++ 17)
• 3 На практике
• 4 Примечания
• 5 Дополнительная литература
• 6 Ссылки
• 7 Внешние ссылки

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

Для циклической группы $G\; \{\backslash \; displaystyle\; G\}$порядка $n\; \{\backslash \; displaystyle\; n\}$, a generator $\alpha \; \{\backslash \; displaystyle\; \backslash \; alpha\}$группы и элемента группы $\beta \; \{\backslash \; displaystyle\; \backslash \; beta\}$, проблема в найти целое число $x\; \{\backslash \; displaystyle\; x\}$такое, что

$\alpha \; x\; =\; \beta .\; \{\backslash \; displaystyle\; \backslash \; alpha\; ^\; \{x\}\; =\; \backslash \; beta\; \backslash ,.\}$

Алгоритм гигантских шагов маленького шага основан на перезаписи $x\; \{\backslash \; displaystyle\; x\}$:

$x\; =\; im\; +\; j\; \{\backslash \; displaystyle\; x\; =\; im\; +\; j\}$

$m\; =\; \lceil \; N\; \rceil \; \{\backslash \; displaystyle\; m\; =\; \backslash \; left\; \backslash \; lceil\; \{\backslash \; sqrt\; \{n\}\}\; \backslash \; right\; \backslash \; rceil\}$

Следовательно, мы имеем:

$\alpha \; x\; =\; \beta \; \{\backslash \; displaystyle\; \backslash \; alpha\; ^\; \{x\}\; =\; \backslash \; beta\; \backslash ,\}$

$\alpha \; im\; +\; j\; =\; \beta \; \{\backslash \; displaystyle\; \backslash \; alpha\; ^\; \{im\; +\; j\}\; =\; \backslash \; бета\; \backslash ,\}$

$\alpha \; j\; знак\; равно\; \beta \; (\alpha \; -\; м)\; я\; \{\backslash \; displaystyle\; \backslash \; alpha\; ^\; \{j\}\; =\; \backslash \; beta\; \backslash \; left\; (\backslash \; alpha\; ^\; \{-\; m\}\; \backslash \; right)\; ^\; \{i\}\; \backslash ,\}$

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

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

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

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

.

Алгоритм C ++ ( C ++ 17)

#include #include #include std :: uint32_t pow_m (std :: uint32_t base, std :: uint32_t exp, std :: uint32_t mod) {// модульное возведение в степень с использованием алгоритма квадратного умножения} /// Вычисляет x так, чтобы g ^ x% mod == h std :: optional babystep_giantstep (std :: uint32_t g, std :: uint32_t h, std :: uint32_t mod) {const auto m = static_cast (std :: ceil (std :: sqrt (mod))); auto table = std :: unordered_map {}; auto e = std :: uint64_t {1} ; // временные значения могут быть больше 32 бит для (auto i = std :: uint32_t {0}; i (e)] = i; e = (e * g)% mod;} const auto factor = pow_m (g, mod-m-1, mod); e = h; for (auto i = std :: uint32_t {}; i (e)); it! = tab le.end ()) {return {i * m + it->second}; } e = (e * коэффициент)% mod; } return std :: nullopt; }

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

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

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

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

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

• Baby step-Giant step - пример исходного кода C