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

Долгое время эффективный алгоритм решения задачи дискретного логарифмирования не был известен и при вычислениях использовались заранее подготовленные таблицы индексов. Пример такой таблицы можно найти, например, в монографии [1, стр. 372].

В 1962 году советским математиком Александром Осиповичем Гельфондом был предложен метод, см. [5, гл. 6, п. З), который позволил вычислять индексы достаточно эффективно при небольших значениях р. В русскоязычной литературе этот метод получил название «метод согласования».

Независимо от этого в 1971 году Даниэль Шенке (Daniel Shanks) предложил^[1] аналогичный метод решения задачи дискретного логарифмирования, получивший название «метод больших и малых шагов» (baby steps, giant steps). В настоящее время в литературе используются оба названия метода.

Итак, рассмотрим сравнение (13.29). Если вычет 6=1 (modp), то, очевидно, выполнено сравнение х = 0 (modm) и наша задача решена.

Во всех остальных случаях определим целое число h = /т]. Поскольку мы ищем величину х, для которой 0 < х < т, мы можем и определить такие целые значения и, v, что.

Выполнено сравнение.

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

Мы организуем перебор следующим образом. Для всех возможных значений v — 0, 1, …, h—1 вычислим вычеты ba^v (mod р) и сохраним их в памяти. Далее, вычисляя (a^h)^u для всех и = 1, …, h, будем сравнивать полученные значения со значениями, сохраненными в памяти. Как только будет найдено равенство, мы определим неизвестные и, v, а следом, используя (13.32), и величину х.

Пример 13.4. Рассмотрим следующую задачу. Необходимо найти величину х, удовлетворяющую сравнению 3^х = 148 (mod 181), если известно, что выполнено условие огбш 3 = 45.

Поскольку показатель величины 3 по модулю 181 равен 45. Следовательно, мы можем определить величину h = [/45] = 7. Составим таблицу возможных значений величины ba^v (mod р), v = 0, 1, …, б для значений а = 3, b = 148.

Теперь составим таблицу значений (a^h)^u при а — 3, h — 7 и и= 1, 2, …, 7.

Легко заметить, что в обеих таблицах содержится одно и то же значение 126. Используя этот факт, мы можем записать сравнение.

следовательно, и = 4, v = 5 и мы получаем, что х = 7 ? 4 — 5 = 23. Проверяя, получим сравнение З²³ = 148 (mod 181).

Укажем некоторые аспекты реализации на ЭВМ метода согласования и одновременно оценим его трудоемкость. На первом шаге мы составляем таблицу, содержащую h значений — величины ba^v (modр) для всех v = 0. 1. Каждый элемент таблицы представляет собой пару значений (v, ba^v), которые сортируются при вставке в таблицу по возрастанию величины вычета ba^v (сортировка производится для оптимизации процедуры поиска значений на втором шаге алгоритма). Для создания таблицы нам потребуется h операций умножения вычетов по модулю р. Кроме того, мы будем выполнять операцию вставки пар значений (v, ba^v) в таблицу.

На втором шаге алгоритма нам необходимо вычислить не более h вычетов a^hu при и = 0, … Л. — 1. Это потребует не более h операций умножения вычетов по модулю р. Следовательно, трудоемкость метода согласования — не более 2h операций с вычетами по модулю р.

• [1] См. Shanks D. Class Number, a Theory of Factorization and Genera //Proceedings Of Symposium Pure Mathematics. — Vol. 20. — AMS: Providence, R. I.- 1971. -pp. 415−440.