Алгоритм Гельфонда — Шенкса (англ. Baby-step giant-step; также называемый алгоритм больших и малых шагов) — в теории групп детерминированный алгоритм дискретного логарифмирования в мульпликативной группе кольца вычетов по модулю простого числа. Был предложен советским математиком Александром Гельфондом в 1962 году и Дэниэлем Шенксом в 1972 году^[1][2][3]. Относится к методам встречи посередине.

Применение

Для модулей специального вида алгоритм Гельфонда — Шенкса является полиномиальным. Задача дискретного логарифмирования представляет большой интерес в области криптосистем с открытым ключом, например, RSA, DSA, Elgamal, Diffie-Hellman, ECDSA, ГОСТ Р 34.10-2001, Rabin и другие. Большинство существующих таких систем основаны на предположении о чрезвычайно высокой вычислительной сложности нахождения дискретного логарифма (вопрос о решении задачи дискретного логарифма за полиномиальное время на персональном компьютере остаётся открытым до сих пор); чем сложнее её решить (чем большее количество операций нужно проделать для нахождения дискретного логарифма), тем более криптобезопасной является пересылка информации. Таким образом, одним из способов повысить сложность задачи дискретного логарифмирования является создание криптосистемы, основанной на группе с большим порядком (где логарифмирование будет происходить по модулю большого простого числа). Данный же алгоритм позволяет в некоторых случаях упростить нахождения показателя степени (уменьшить количество шагов) при вычислении по модулю простого числа, в самом благоприятном случае в квадратный корень раз^[4].

Задача дискретного логарифмирования

Пусть задана циклическая группа ${\displaystyle G}$ с образующим ${\displaystyle g}$, содержащая ${\displaystyle n}$ элементов. Целое число ${\displaystyle x}$ (в диапазоне от ${\displaystyle 0}$ до ${\displaystyle n-1}$) называется дискретным логарифмом элемента ${\displaystyle h\in G}$ по основанию ${\displaystyle g}$, если выполняется соотношение:

${\displaystyle g^{x}=h.}$

Задача дискретного логарифмирования — по заданным ${\displaystyle h}$, ${\displaystyle g}$ определить ${\displaystyle x}$.

Формально задача дискретного логарифмирования ставится следующим образом^[5]:

${\displaystyle {\begin{cases}{\text{Input:}}\quad &g,h,n\in \mathbb {N} \\{\text{Output:}}\quad &x\in \mathbb {N} :\ g^{x}\equiv h{\pmod {n}}\\\end{cases}}}$

при условии, что ${\displaystyle x}$ может не существовать, а также ${\displaystyle n}$ может быть как простым числом, так и составным.

Теория

Идея алгоритма состоит в выборе оптимального соотношения времени и памяти, а именно в усовершенствованном поиске показателя степени.

Пусть задана циклическая группа ${\displaystyle G}$ порядка ${\displaystyle n}$, генератор группы ${\displaystyle \alpha }$ и некоторый элемент группы ${\displaystyle \beta }$. Задача сводится к нахождению целого числа ${\displaystyle x}$, для которого выполняется

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

Алгоритм Гельфонда — Шенкса основан на представлении ${\displaystyle x}$ в виде ${\displaystyle x=i\cdot m-j}$, где ${\displaystyle m=\left\lfloor {\sqrt {n}}\right\rfloor +1}$, и переборе ${\displaystyle 1\leq i\leq m}$ и ${\displaystyle 0\leq j<m}$. Ограничение на ${\displaystyle i}$ и ${\displaystyle j}$ следует из того, что порядок группы не превосходит ${\displaystyle m}$, а значит указанные диапазоны достаточны для получения всех возможных ${\displaystyle x}$ из полуинтервала ${\displaystyle \left[0;m\right)}$. Такое представление равносильно равенству

${\displaystyle \alpha ^{im}=\beta \alpha ^{j}\,.}$

(1)

Алгоритм предварительно вычисляет ${\displaystyle \alpha ^{im}}$ для разных значений ${\displaystyle i}$ и сохраняет их в структуре данных, позволяющей эффективный поиск, а затем перебирает всевозможные значения ${\displaystyle j}$ и проверяет, если ${\displaystyle \beta \alpha ^{j}}$ соответствует какому-то значению ${\displaystyle i}$. Таким образом находятся индексы ${\displaystyle i}$ и ${\displaystyle j}$, которые удовлетворяют соотношению (1) и позволяют вычислить значение ${\displaystyle x=i\cdot m-j}$ ^[6].

Алгоритм

Вход: Циклическая группа ${\displaystyle G}$ порядка ${\displaystyle n}$, генератор ${\displaystyle \alpha }$ и некоторый элемент ${\displaystyle \beta }$.

Выход: Число ${\displaystyle x}$, удовлетворяющее ${\displaystyle \alpha ^{x}=\beta }$.

1. ${\displaystyle m}$ ← ${\displaystyle [{\sqrt {n}}]+1}$
2. Вычислить ${\displaystyle \gamma }$ ← ${\displaystyle \alpha ^{m}}$.
3. Для ${\displaystyle i}$ от ${\displaystyle 0}$ до ${\displaystyle m}$:
   1. Записать в таблицу (${\displaystyle i}$, ${\displaystyle \gamma }$). (см. раздел «Реализация»)
   2. ${\displaystyle \gamma }$ ← ${\displaystyle \gamma }$ • ${\displaystyle \alpha ^{m}}$
4. Для любого ${\displaystyle j}$ где ${\displaystyle 0}$ ≤ ${\displaystyle j}$ < ${\displaystyle m}$:
   1. Вычислить ${\displaystyle \alpha }$.
   2. Проверить, содержится ли ${\displaystyle \beta \alpha ^{j}}$ в таблице.
   3. Если да, вернуть ${\displaystyle im}$ — ${\displaystyle j}$.
   4. Если нет, продолжить выполнение цикла^[1][2][6].

Обоснование алгоритма

Нужно доказать, что одинаковые элементы в таблицах обязательно существуют, то есть найдутся такие ${\displaystyle i}$ и ${\displaystyle j}$, что ${\displaystyle g^{mi}=\beta \cdot g^{j}=g^{x+j}}$. Это равенство имеет место в случае ${\displaystyle mi=x+j{\pmod {n}}}$, или ${\displaystyle x=mi-j{\pmod {n}}}$. При ${\displaystyle 1\leq i\leq m}$, ${\displaystyle 1\leq j\leq m}$ выполнено неравенство ${\displaystyle 0\leq mi-j\leq m^{2}-1}$. Для различных пар ${\displaystyle (i_{1},j_{1})}$ и ${\displaystyle (i_{2},j_{2})}$ имеем ${\displaystyle mi_{1}-j_{1}\neq mi_{2}-j_{2}}$, так как в противном случае получилось бы ${\displaystyle m(i_{1}-i_{2})=(j_{1}-j_{2})}$, что при указанном выборе ${\displaystyle i_{1},i_{2}}$ возможно только в случае ${\displaystyle i_{1}=i_{2}}$, и, следовательно, ${\displaystyle j_{1}=j_{2}}$. Таким образом, выражения ${\displaystyle mi-j}$ принимают все значения в диапазоне от ${\displaystyle 0}$ до ${\displaystyle m^{2}-1}$, который, в силу того, что ${\displaystyle m^{2}>n}$, содержит все возможные значения ${\displaystyle x}$ от ${\displaystyle 0}$ до ${\displaystyle n-1}$. Значит, для некоторых ${\displaystyle i}$ и ${\displaystyle j}$ имеет место равенство ${\displaystyle x=mi-j{\pmod {n}}}$^[2].

Оценка сложности алгоритма

Допустим, что необходимо решить ${\displaystyle h=ng}$, где ${\displaystyle h}$ и ${\displaystyle g}$ — целые положительные числа меньше ${\displaystyle 100}$. Один из способов — перебрать последовательно ${\displaystyle n}$ от ${\displaystyle 1}$ до ${\displaystyle 100}$, сравнивая величину ${\displaystyle n\cdot g}$ с ${\displaystyle h}$. В худшем случае нам потребуется ${\displaystyle 100}$ шагов (когда ${\displaystyle n=99}$). В среднем это займет ${\displaystyle 50}$ шагов. В другом случае, мы можем представить ${\displaystyle n}$ как ${\displaystyle n=10a-b}$. Таким образом, задача сводится к нахождению ${\displaystyle a}$ и ${\displaystyle b}$ . В этом случае можно переписать задачу как ${\displaystyle h=(10a-b)g}$ или ${\displaystyle h+bg=10ag}$. Теперь мы можем перебрать все возможные значения ${\displaystyle a}$ в правой части выражения. В данном случае это все числа от ${\displaystyle 1}$ до ${\displaystyle 10}$. Это, так называемые, большие шаги. Известно, что одно из полученных значение для ${\displaystyle a}$ — искомое. Мы можем записать все значения правой части выражения в таблице. Затем мы можем посчитать возможные значения для левой части для различных значений ${\displaystyle b}$. Такими являются все числа от ${\displaystyle 0}$ до ${\displaystyle 9}$ из которых одно является искомым, и вместе с правильным значением правой части дает искомый результат для ${\displaystyle n}$. Таким образом, задача сводится к перебору различных значений левой части и поиск их в таблице. Если нужное значение в таблице найдено, то мы нашли ${\displaystyle b}$, и, следовательно, соответствующее ${\displaystyle n=10a+b}$. Данная иллюстрация демонстрирует скорость работы алгоритма. В среднем выполняется ${\displaystyle 1.5{\sqrt {n}}}$ операций. В худшем случае требуется ${\displaystyle 2{\sqrt {n}}}$ операций ^[3].

Пример

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

Пример 1

Пусть требуется решить сравнение ${\displaystyle 2^{x}\equiv 28{\pmod {37}}}$. Основная идея: в начале требуется составить таблицу для «больших». Мы выберем ${\displaystyle m=7}$ ← (${\displaystyle {\sqrt {36}}+1)}$. ${\displaystyle i}$ пробегает все значения от ${\displaystyle 1}$ до ${\displaystyle 7}$.

Далее будем подбирать ${\displaystyle j}$ такое, что ${\displaystyle \beta \alpha ^{j}{\pmod {37}}}$ уже находится в таблице («маленькие шаги»).

Видно, что выражение для ${\displaystyle j=1}$ уже находится в первой таблице. Отсюда находим, что ${\displaystyle j=1,i=5}$. Соответствующее значение ${\displaystyle x=mi-j=7}$·${\displaystyle 5-1=34}$. Среднее число шагов — ${\displaystyle 1.5{\sqrt {37}}\approx 9}$. Нам понадобилось ровно ${\displaystyle 9}$ шагов.

Пример 2

Пусть известно ${\displaystyle 5^{x}\equiv 3{\pmod {23}}}$. В начале создадим и заполним таблицу для «больших шагов». Выберем ${\displaystyle m=5}$ ← (${\displaystyle {\sqrt {16}}+1}$). Затем ${\displaystyle i}$ пройдёт от ${\displaystyle 1}$ до ${\displaystyle 5}$.

Найдем подходящее значение ${\displaystyle j}$ для ${\displaystyle 3\cdot 5^{j}\ {\bmod {\ }}23}$, чтобы значения в обеих таблицах совпали

Видно, что во второй таблице для ${\displaystyle j=4}$, такое значение уже находится в первой таблице. Находим ${\displaystyle x=mi-j=5\cdot 4-4=16}$.

Пример 3

Пусть задано ${\displaystyle 6^{x}\equiv 7531{\pmod {8101}}}$. Необходимо вычислить ${\displaystyle x}$. В начале создадим и заполним таблицу для «больших шагов». Выберем ${\displaystyle m=91}$ ← (${\displaystyle {\sqrt {8101}}+1}$). Затем мы просто проитерируем ${\displaystyle i}$ от ${\displaystyle 1}$ до ${\displaystyle 91}$.

Найдем подходящее значение ${\displaystyle j}$ для ${\displaystyle 7531\cdot 6^{j}\ {\bmod {\ }}8101}$.

Видно, что во второй таблице для ${\displaystyle j=45}$, соответствующее значение уже находится в первой таблице. Отсюда находим ${\displaystyle x=mi-j=91\cdot 74-45=6689}$. В среднем необходимо ${\displaystyle 1.5{\sqrt {8101}}\approx 135}$ шагов. Нам понадобилось ${\displaystyle 136}$ шагов.

Реализация

Существует способ улучшить производительность алгоритма Гельфонда — Шенкса. Он заключается в использовании эффективной схемы доступа к таблице. Лучший способ — использование хеш-таблицы. Следует производить хеширование по второй компоненте, а затем выполнять поиск по хешу в таблице в основном цикле по ${\displaystyle \gamma }$. Так как доступ и добавление элементов в хеш-таблицу работает за время ${\displaystyle O(1)}$ (константа), то асимптотически это не замедляет алгоритм.

Время работы алгоритма оценивается как ${\displaystyle O({\sqrt {n}})}$, что намного лучше, чем время работы ${\displaystyle O(n)}$ полного перебора показателей степени^[4].

Особенности

• Алгоритм Гельфонда — Шенкса работает для произвольной конечной циклической группы.
• Нет необходимости знать порядок группы ${\displaystyle G}$ заранее. Алгоритм также работает, если ${\displaystyle n}$ — верхняя граница порядка группы.
• Обычно алгоритм Гельфонда — Шенкса используется для групп, у которых порядок — простое число. Если порядком является составное число, то рекомендуется использование алгоритма Полига — Хеллмана^[6].
• Алгоритму Гельфонда — Шенкса требуется ${\displaystyle O(n)}$ памяти. Возможно выбрать меньшее ${\displaystyle m}$ на первом шаге алгоритма. Это увеличивает время работы программы до ${\displaystyle O(n/m)}$. Также возможно использование ρ-метода Полларда для дискретного логарифмирования, который работает за то же самое время, но требует малое количество памяти^[6].

Примечания