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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

 

 

 

(1)

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

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

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

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

  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]

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

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

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

Пример 1

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

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

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

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

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

Пример 2

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

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

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

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

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

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

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

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

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

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

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

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

  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..

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