Введение в криптографию
[an error occurred while processing this directive]

Дискретное логарифмирование


Пусть  - нечетное простое число. Еще Эйлер знал, что мультипликативная группа кольца циклична, т.е. существуют такие целые числа , что сравнение

(22)

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

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

арифметических операций (см. []), где  - некоторая положительная постоянная. Это сравнимо со сложностью наиболее быстрых алгоритмов разложения чисел на множители. Конечно, указанная оценка сложности получена при условии справедливости ряда достаточно правдоподобных гипотез.

Говоря о сложности задачи дискретного логарифмирования, мы имели в виду ``общий случай''. Ведь и большое целое число легко может быть разложено на простые сомножители, если все эти сомножители не очень велики. Известен алгоритм, позволяющий быстро решать задачу дискретного логарифмирования, если есть произведение малых простых чисел.

Пусть  - простое число, делящее . Обозначим

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

. Если не велико и целое число удовлетворяет сравнению

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

Допустим, что , . Алгоритм последовательно строит целые числа , , для которых выполняется сравнение




- Начало -  - Назад -  - Вперед -


[an error occurred while processing this directive]