Эта статья является кандидатом в добротные статьи

Алгоритм Гельфонда — Шенкса

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Алгоритм Шенкса»)
Перейти к: навигация, поиск

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

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

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

Дэниэль Шенкс — математик, предложивший алгоритм Гельфонда — Шенкса в 1972 году.
Александр Осипович Гельфонд — математик, предложивший алгоритм Гельфонда — Шенкса в 1962 году.

Пусть задана циклическая группа с образующим , содержащая элементов. Целое число (в диапазоне от до ) называется дискретным логарифмом элемента по основанию , если выполняется соотношение:

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

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

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

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

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

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

Алгоритм Гельфонда — Шенкса основан на представлении в виде , где , и переборе и . Ограничение на и следует из того, что порядок группы не превосходит , а значит указанные диапазоны достаточны для получения всех возможных из полуинтервала . Такое представление равносильно равенству

 

 

 

 

(1)

Алгоритм предварительно вычисляет для разных значений и сохраняет их в структуре данных, позволяющей эффективный поиск, а затем перебирает всевозможные значения и проверяет, если соответствует какому-то значению . Таким образом находятся индексы и , которые удовлетворяют соотношению (1) и позволяют вычислить значение [5].

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

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

Выход: Число , удовлетворяющее .

  1. Вычислить .
  2. Для от до :
    1. Записать в таблицу (, ). (см. раздел «Реализация»)
  3. Для любого где < :
    1. Вычислить .
    2. Проверить, содержится ли в таблице.
    3. Если да, вернуть  — .
    4. Если нет, продолжить выполнение цикла[1][2][5].

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

Нужно доказать, что одинаковые элементы в таблицах обязательно существуют, то есть найдутся такие и , что . Это равенство имеет место в случае , или . При , выполнено неравенство . Для различных пар и имеем , так как в противном случае получилось бы , что при указанном выборе возможно только в случае , и, следовательно, . Таким образом, выражения принимают все значения в диапазоне от до , который, в силу того, что , содержит все возможные значения от до . Значит, для некоторых и имеет место равенство [2].

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

Допустим, что необходимо решить , где и  — целые положительные числа меньше . Один из способов — перебрать последовательно от до , сравнивая величину с . В худшем случае нам потребуется шагов (когда ). В среднем это займет шагов. В другом случае, мы можем представить как . Таким образом, задача сводится к нахождению и . В этом случае можно переписать задачу как или . Теперь мы можем перебрать все возможные значения в правой части выражения. В данном случае это все числа от до . Это, так называемые, большие шаги. Известно, что одно из полученных значение для  — искомое. Мы можем записать все значения правой части выражения в таблице. Затем мы можем посчитать возможные значения для левой части для различных значений . Такими являются все числа от до из которых одно является искомым, и вместе с правильным значением правой части дает искомый результат для . Таким образом, задача сводится к перебору различных значений левой части и поиск их в таблице. Если нужное значение в таблице найдено, то мы нашли , и, следовательно, соответствующее . Данная иллюстрация демонстрирует скорость работы алгоритма. В среднем выполняется операций. В худшем случае требуется операций [3].

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

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

Пример 1

Пусть требуется решить сравнение . Основная идея: в начале требуется составить таблицу для «больших». Мы выберем ← (. пробегает все значения от до .

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

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

0 1
· 28 19

Видно, что выражение для уже находится в первой таблице. Отсюда находим, что . Соответствующее значение ·. Среднее число шагов — . Нам понадобилось ровно шагов.

Пример 2

Пусть известно . В начале создадим и заполним таблицу для «больших шагов». Выберем ← (). Затем пройдёт от до .

1 2 3 4 5
20 9 19 12 10

Найдем подходящее значение для , чтобы значения в обеих таблицах совпали

1 2 3 4
· 15 6 7 12

Видно, что во второй таблице для , такое значение уже находится в первой таблице. Находим .

Пример 3

Пусть задано . Необходимо вычислить . В начале создадим и заполним таблицу для «больших шагов». Выберем ← (). Затем мы просто проитерируем от до .

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

Найдем подходящее значение для .

44 45
· 2893 1156

Видно, что во второй таблице для , соответствующее значение уже находится в первой таблице. Отсюда находим . В среднем необходимо шагов. Нам понадобилось шагов.

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

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

Время работы алгоритма оценивается как , что намного лучше, чем время работы полного перебора показателей степени[6].

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

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

  1. 1 2 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. 1 2 3 И. А. Панкратова. Теоретико-числовые методы в криптографии: Учебное пособие. — Томск: ТГУ, 2009. — С. 90-98. — 120 с..
  3. 1 2 В.И. Нечаев. Элементы криптографии. Основы теории защиты информации. — М.: Высшая школа, 1999. — С. 61-67. — 109 с. — ISBN 5-06-003644-8..
  4. Yan, Song Y. Primality testing and integer factorization in public-key cryptography. — 2. — Springer, 2009. — С. 257-260. — 374 с. — ISBN 978-0-387-77267-7..
  5. 1 2 3 4 Глухов М. М, Круглов И. А., Пичкур А. Б., Черемушкин А. В. Введение в теоретико- числовые методы криптографии. — 1 изд.. — СПб: Лань, 2010. — С. 279-298. — 400 с. с. — ISBN 978-5-8114-1116-0..
  6. D. C. Terr. A modification of Shanks’ baby-step giant-step algorithm. — Mathematics of Computation. — 2000. — Т. 69. — С. 767–773..

Литература[править | править вики-текст]

  • А.О. Гельфонд, Ю.В. Линник. Элементарные методы в аналитической теории чисел. — М.: Физматгиз, 1962. — 272 с.