Метод Госпера. 
Криптографические методы защиты информации

Алгоритм Флойда поиска циклов в последовательностях является простым, но не самым оптимальным. Для задачи дискретного логарифмирования наиболее эффективным методом^[1] является алгоритм, предложенный Биллом Госпером (Ralph William Gosper, Jr.). В алгоритме Госпера для поиска двух совпадающих элементов последовательности (13.40).

производится сравнение элемента z_n с элементами некоторого множества М (п).

Для начала напомним, что функция V2(z) возвращает наибольшую степень двойки, делящую величину г. Теперь фиксируем значение п > 0 и поместим в множество М (п) элементы z_no, z_ni, … последовательности (13.40) с условием.

для всех возможных значений к = 0, 1, ____Из определения следует, что множество М (п) конечно, содержит не более Llog₂ п + 1 чисел и отличается от множества М (п+1) лишь одним элементом.

Теорема 13.8 (Госпер). Пусть заданы параметры X и т, определяющие длину подхода к циклу и длину цикла последовательности (13.40). Тогда найдутся натуральные индексы г и п = г + г такие, что

• 1. элемент z_r принадлежит множеству М (п) и выполнено равенство z_n = z_r,
• 2. А + т^тг<�А + 2 т.

Утверждение теоремы в явном виде задает нам множество М (п), в котором содержится элемент а_г такой, что а_г = а_п. Более того, теорема позволяет получить оценку сверху на максимальное число элементов последовательности (13.40), которые необходимо вычислить для нахождения указанного равенства.

Мы строим множество М (п) следующим образом: разобьем последовательность (13.40) на несколько подпоследовательностей так, что первая подпоследовательность содержит все элементы с индексами г такими, что г +1 нечетно, вторая — элементы с индексами г такими, что г + 1 делится в точности на двойку, третья — элементы с индексами г такими, что г+1 делится в точности на четверку и т. д. Тогда в множество М (п) входит, но одному элементу из каждой подпоследовательности с максимальным индексом, не превосходящим п. Например, для п = 16 множество М (16) имеет вид

Каждый элемент Т представляет собой структуру, храпящую элемент множества А, а также два элемента А, В, определенные равенствами (13.41) и являющиеся суммами соответствующих коэффициентов а,; и 0i. Мы будем обозначать эти данные соответственно Ш, Т[А) и Т_г[В.

Алгоритм 13.10 (Алгоритм Госпера) Вход: Простое число р, вычеты а, Ь, удовлетворяющие заданному сравнению а^х = b (mod р), где ord_p" = тп, а также параметр s > 3 и отображение f (x), задаваемое наборами вычетов а, …, at₃-i, /За, …, P_s-i- Выход: Дискретный логарифм х = log" Ь (mod тп).

• 1. Выбрать случайное ко такое, что 0 < ко < тп и определить 2 = а^ко (modр), а также п = 0, t = 1, А = ко, В = 0 и Т₀[г] = х, Т₀А] = к₀, То[В = 0.
• 2. Вычислить z = f (z) и А = А + а₍; (mod тп), В = В + (mod тп) для величины г, удовлетворяющей сравнению i = z (mod s).
• 3. Для всех г от 0 до t — 1 выполнить
• 3.1. Если 2 = Ti[z, то вычислить х = щв]^в (^ПК)<1^т) и завершить алгоритм.
• 4. Определить п = п + 1пк = ^(п).
• 5. Если к = t, то вычислить 1 = 1 + 1.
• 6. Определить [z = z, Т^[А] = А, Тк[В] = В и вернуться на шаг 2.
• ?

Как следует из утверждения теоремы 13.8, приведенный алгоритм затратит на нахождение неизвестной величины 2 не более двух периодов последовательности 20,21, … Однако асимптотическая оценка метода Госпера совпадает с оценкой метода ПоллардаФлойда и составляет 0(у/тп).

Задачи и упражнения

• 1. Построить таблицу всех простых чисел, не превосходящих
• 250.
• 2. Используя теорему Лемера, построить простое число р в интервале 8000 < р < 9000.
• 3. Используя метод Ферма, разложите на множители числа 197 881, 295 543 и 327 653.
• 4. Реализуйте на практике алгоритм квадратичного решета с несколькими многочленами.
• 5. Докажите утверждения леммы 13.2.
• 6. Решите задачу дискретного логарифмирования
• 2^х ее 103 (mod 443), 2^х ее 120 (mod 467),
• 3^х ее 267 (mod 487), 3^х ее 118 (mod 521).

Дополнительная литература к 13-й главе

• 1. Бухштаб А.А. Теория чисел. — М.:Просвещение. — 1966.
• 2. Галочкин А.И., Нестеренко Ю. В. и Шидловский А.Б. Введение в теорию чисел. — М.:Изд-во Московского Университета. — 1984. — 152 с.
• 3. Василенко О. Н Теоретико-числовые алгоритмы в криптографии. — М.:МЦМНО. — 2003. — 328с.
• 4. Нестеренко А.Ю. Теоретико-числовые алгоритмы в криптографии. — М.:МИЭМ. — 2012.
• 5. Нечаев В.И. Элементы криптографии (Основы теории защиты информации). — М.:Высш.шк. — 1999. — 109 с.

• [1] Обзор методов поиска длин циклов в последовательностях и их криптографических приложений может быть найден в статье Нестеренко А. Ю. Алгоритмыпоиска длин циклов в последовательностях и их приложения // Фундаментальная и прикладная математика. — №. 6. -Т. 16. -2010. — с. 109−122.