Алгоритм Полига — Хеллмана

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 22:17, 17 мая 2016.

Постановка задачи: найти в поле

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

Определения

TemplateDifinitionIcon.svg Определение «Гладкие числа»
Числа, простые делители которых малы.

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

Первый этап алгоритма

Для простого составл. табл.:

Эта таблица значений является основой для вычисления дискретного логарифма любого элемента поля (кроме нулевого, разумеется).

Второй этап алгоритма

Наша цель - найти такой элемент , что . Пусть имеется разложение числа на простые множители. Достаточно найти , для каждого делящего .

Пусть

Для того, чтобы найти мы вычисляем . Из равенства следует, что . Сравниваем со значениями полученной ранее таблицы и полагаем равным тому значению , при котором

Далее, чтобы найти мы заменяем на . Тогда имеет дискретный логарифм . Так как - это -я степень, то получаем и . Значит, мы можем сравнить с и положить равным тому , при котором .

Аналогично, для любого полагаем и получаем равным тому , при котором .

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

Пример

TemplateExampleIcon.svg Пример Найти дискретный логарифм по основанию в .

Имеем . Вычисляем и , .

Далее, , и .

Пусть теперь .

Сначала возьмем и найдем вычет , который запишем как .

Имеем , и, следовательно, .

Далее, , и поэтому , то есть .

Теперь берем и находим вычет , который записываем как .

Чтобы найти , вычисляем .

Таким образом .

Затем вычисляем и получаем .

Итак, .

Остается найти единственный элемент , при котором и .

Это .

Таким образом в .


Литература

1.Н. Коблиц. Курс теории числе и криптографии. — М. : Научное изд-во ТВП, 2001. — С. 254. — ISBN 5-09-002630-0.