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

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

(22)

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

В разделе 2 мы описали алгоритм, позволяющий по заданному числу x достаточно быстро вычислять .

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