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

Дискретное логарифмирование - часть 2


(23)

Так как выполняется сравнение

, то найдется целое число , для которого

. При таком выборе сравнение () с , очевидно, выполняется. Предположим, что найдено число , удовлетворяющее сравнению (). Тогда определим с помощью сравнения

(24)

и положим . Имеют место сравнения

(25)

означающие справедливость () при .

При сравнение () означает в силу (), что

. Целое число есть первообразный корень по модулю , поэтому имеем

и

Если

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

, , и, с помощью китайской теоремы об остатках, вычет , т.е. решить сравнение ().

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

(26)

Логарифмы по произвольному основанию могут быть вычислены с помощью тождества

(27)

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

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




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


[an error occurred while processing this directive]