Алгоритм Шенкса

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Для модулей специального вида алгоритм Шенкса является полиномиальным. Задача дискретного логарифмирования представляет большой интерес в области криптосистем с открытым ключом. Большинство существующих алгоритмов нахождения дискретного логарифма основаны на предположении о чрезвычайно высокой вычислительной сложности (вопрос о решении задачи дискретного логарифма за полиномиальное время на персональном компьютере остаётся открытым до сих пор); чем сложнее её решить, тем более криптобезопасной является пересылка информации. Таким образом, одним из способов повысить сложность задачи дискретного логарифмирования является создание криптосистемы, основанной на группе с большим порядком.

Задача дискретного логарифмирования[править | править вики-текст]

Дэниэль Шенкс — автор опубликованного в 1972 году алгоритма «больших и малых шагов».

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

 g^x = h.

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

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


\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}

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

Теория[править | править вики-текст]

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

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

\alpha^x = \beta\,.

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

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

 

 

 

 

(1)

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

Алгоритм[править | править вики-текст]

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

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

  1. m ← Пол(√n)+1
  2. Вычислить γ ← αm.
  3. Для i от 0 до m:
    1. Записать в таблицу (i, γ). (см. раздел «Реализация»)
    2. γ ← γ • αm
  4. Для любого j где 0 ≤ j < m:
    1. Вычислить αj.
    2. Проверить, содержится ли βαj в таблице.
    3. Если да, вернуть im — j.
    4. Если нет, продолжить выполнение цикла.

Оценка сложности алгоритма[править | править вики-текст]

Question mark2.svg
Нерешённые проблемы информатики: Может ли задача дискретного логарифмирования решаться за полиномиальное время?[3]

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

Пример[править | править вики-текст]

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

Пример 1

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

i 1 2 3 4 5 6 7
2im = 17i 17 30 29 12 19 27 15

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

j 0 1
βαj=28·2j 28 19

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

Пример 2

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

i 1 2 3 4 5 6 73 74 91
6im = 7477i 7477 528 2669 3350 7759 2782 3789 1156 88

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

j 44 45
βαj=7531·6j 2893 1156

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

Реализация[править | править вики-текст]

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

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

Особенности[править | править вики-текст]

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. D. Shanks. The infrastructure of a real quadratic field and its applications. Proceedings of the Number Theory Conference. — University of Colorado, Boulder,, 1972. — С. pp. 217-224..
  2. Yan, Song Y. Primality testing and integer factorization in public-key cryptography. — 2. — Springer, 2009. — С. 257-260. — 374 с. — ISBN 978-0-387-77267-7..
  3. [1] (англ.)
  4. D. C. Terr. A modification of Shanks’ baby-step giant-step algorithm. — Mathematics of Computation. — 2000. — Т. 69. — С. 767–773..

Ссылки[править | править вики-текст]