Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
114
ГЛ. IV. ОТКРЫТЫЙ ключ
Теперь должно быть понятно, как можно продолжить этот процесс, чтобы получить все Xq, Xi,... ,ха-1- А именно, для каждого г = 1, 2,..., а — 1 полагаем
дискретный логарифм этого выражения сравним по модулю ра с хгр' + ••¦ + xa_ipa l. Так как у± является р'-й степенью, то у\ч р = 1 и у\ч "F = Ь ч-і^-г і\ч ,if __ j .и hv _ Гр)Х>. Поэтому мы
(9-l)/pl+1
полагаем х; равным тому j, при котором у] = rpj.
Завершив этот процесс, мы получим х (mod ра). Повторив такие вычисления для каждого p\(q — 1), мы воспользуемся китайской теоремой об остатках и найдем х.
Этот алгоритм хорошо работает, когда все простые делители числа q—l малы. Очевидно, однако, что для составления таблицы {rpj}
(q-l)/p,+1 _
и сравнения величин у- с ее элементами потребуется много
времени, если q—l имеет большой простой делитель. (Под «большим» понимается число хотя бы в 20 разрядов. Если p\(q — 1) по порядку меньше 10 , то можно использовать комбинацию алгоритма Силвера-Полига-Хеллмана и алгоритма, использующего метод «больших и малых шагов» Шэнкса; см. с. 9 и с. 575-576 второго тома книги Кнута.)
Пример 4. Найти дискретный логарифм 28 по основанию 2 в F37, используя алгоритм Силвера-Полига-Хеллмана (2 является порождающим элементом в F37).
2 2 18
Решение. Имеем 37 — 1 = 2 ¦ 3 . Вычисляем 2 =1 (mod 37) и r2io = 1, Tiд = — 1. (При р = 2 всегда {г^j} = {±1}.) Далее, 23б/з ^ 26 (-mod 22-зб/з ^ 10 ^mod и _ |1)26)10т_ Пусть
теперь 28 = Iх (mod 37). Сначала возьмем р = 2 и найдем вычет X (mod 4), который запишем как X0 + 2Xi • Имеем 2836//2 = 1 (mod 37), и, следовательно, X0 = 0. Далее, 2836//4 = — 1 (mod 37), и поэтому Х\ = 1, т.е. X = 2 (mod 4). Теперь берем р = 3 и находим вычет х (mod 9), который записываем как X0 + 3X1. (Разумеется, для каждого р значения Xi свои.) Чтобы найти х0, вычисляем 2836//3 = 26 (mod 37). Таким образом, X0 = 1. Затем вычисляем (28/2)36//9 = 144 = 10 (mod 37) и получаем Xi = 2. Итак, х = 1 + 2- 3 = 7 (mod 9). Остается найти единственный элемент X (mod 36), при котором х = 2 (mod 4) и х = 1 (mod 9). Это X = 34. Таким образом, 28 = 234 в F37.
Индексный алгоритм дискретного логарифмирования. Читатель может пропустить этот раздел или прочитать его бегло и вер-
§ 3. ДИСКРЕТНОЕ ЛОГАРИФМИРОВАНИЕ
115
нуться к нему потом, при работе с §V.3, поскольку индексный алгоритм вычисления дискретных логарифмов в конечных полях имеет много общего с методом факторных баз для разложения больших целых чисел.
Здесь мы будем предполагать, что q = рп есть весьма большая степень малого простого pub — порождающий элемент группы F*. Индексный алгоритм для любого у Є F* находит такой вычет X (mod q — 1), что у = b .
Пусть J(X) Є Fp[X] — неприводимый многочлен степени п. Тогда F9 изоморфно кольцу вычетов YP[X]/J(X). Любой элемент Yp[X]/J(X) может быть записан (единственным образом) как многочлен а(Х) ? Fp[X] степени не выше п — 1. В частности, основание b = Ь(Х) — тоже многочлен: «константы» являются элементами в Fp С F9.
Заметим сначала, что о = о является порождающим
элементом группы Fp (см. упражнение 17 к §11.1). Значит, решение задачи дискретного логарифмирования в F* (по основанию У) дает значения дискретных логарифмов этих констант по основанию Ь. Так как по условию р мало, то таблицу таких дискретных логарифмов легко составить. В важном частном случае р = 2 единственной ненулевой константой является 1, и ее дискретный логарифм по любому основанию равен 0. Далее будем предполагать, что можно легко найти дискретный логарифм любой константы.
До конца этого раздела будем через inda(X) (от слова «index») обозначать дискретный логарифм а(Х) Є F9 по основанию Ь(Х). Основание Ь(Х) зафиксировано, поэтому оно не вошло в обозначение.
Индексный алгоритм состоит из двух основных этапов. Первый этап мы называем «предварительным», поскольку он не зависит от элемента у(Х) Є F*, логарифм которого мы хотим вычислить. Этот этап выполняется один раз и его результаты можно многократно использовать при вычислении дискретных логарифмов по фиксированному основанию Ь(Х). (Напомним, что аналогичный предварительный этап имеется и в алгоритме Силвера-Полига-Хеллмана — это составление таблицы {rpj}.)
Сначала выберем подмножество В С F9, которое будет служить нам «базисом». Обычно В состоит из всех нормированных неприводимых многочленов над Fp степени не выше т, где т < п определяется некоторым оптимальным образом так, чтобы множество В имело подходящий размер h = //(В) промежуточного порядка между р = #(Fp) и q = рп = ¦//(Yg). Предварительный этап состоит в нахождении дискретных логарифмов для всех а(Х) Є В и заключается в следующем.
116
гл. IV. ОТКРЫТЫЙ ключ
Выберем случайное целое t между 1 и q — 2 и вычислим 6* Є F?, т.е. вычислим такой многочлен с(Х) Є Fp[X] степени ниже п, что
с(Л') = Ь(ХУ (mod /(X)).
(При этом используется метод повторного возведения в квадрат с приведением после каждого шага по модулю /(X).) Вынеся за скобки старший коэффициент с0 в с(х), проверяем, можно ли полученный нормированный многочлен представить в виде произведения многочленов а(Х) Є В, т.е. может ли с(Х) быть записан в виде
