Метод Нечаева. 
Криптографические методы защиты информации

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

в случае, когда нам известно полное разложение показателя элемента а на простые сомножители, то есть т = q±^l •? ? г/" «, где q, — различные простые числа, а а* — некоторые натуральные числа. Фиксируем некоторый индекс г, 1 < i < п, и определим вычет т.

c-i сравнением с_г = a⁴*' (modр). Поскольку ord_pа — т, то для вычета с, выполнено условие ord_p с, =.

С другой стороны, возводя в сравнении (13.38) правую и левую части в степень получим сравнение.

^*.

Поскольку показатель элемента с,; равен qf^l, то мы можем воспользоваться алгоритмом 13.8 и найти величину ау, сравнимую с х но модулю щ^г. Проведенные нами рассуждения верны для любого индекса г, следовательно, мы можем для каждого i найти величину Хг, а после воспользоваться китайской теоремой об остатках и найти величину х.

Таким образом, неизвестное х удовлетворяет системе сравнений.

где дискретные логарифмы ау удовлетворяют сравнениям (13.39). Следует добавить, что метод решения сравнения (13.38) для слу;

чая, когда показатель элемента, а есть составное число, был впервые найден Василием Ильичом Нечаевым в 1965 году, см. [5, гл. 6, п.3|.

Пример 13.5. Рассмотрим еще раз задачу из примера 13.4 и найдем х, удовлетворяющий сравнению 3х = 148 (mod 181). Поскольку нам известно, что ordigi 3 = 45 = З2 • 5, мы будем искать х как решение системы сравнений.

где х'1 и Х'2 удовлетворяют сравнениям.

Первое сравнение получено путем возведения правой и левой частей исходного сравнения в степень З2, второе сравнение — путем возведения в степень 5.

Решим первое сравнение. Поскольку ordigi 135 = 4f = 5, мы можем в явном виде выписать множество возможных степеней вычета 135 по модулю 181.

Из таблицы сразу следует необходимое значение.

Для решения второго сравнения 63х = 65 (mod 181) воспользуемся алгоритмом 13.8. В нашем случае значения параметров алгоритма равны п = 2 и q = 3, поэтому мы будем искать неизвестное х в виде х = хо + 3×1.

Определим константы.

Величина хо является решением сравнения 132х = 48 (mod 181). Поскольку ordigi 132 = 3, то 1322 = 48 (mod 181), 1323 = 1 (mod 181) и мы можем сразу определить хо = 2.

Прежде чем вычислять х, определим величину /Д, удовлетворяющую сравнению.

Мы получили, что величина xi является решением сравнения 132х = 132 (mod 181), откуда сразу вытекает равенство xi = 1 и тот факт, что решение второго сравнения равно 5.

Возвратимся к исходному сравнению 3* = 148 (mod 181) и найдем неизвестное х из системы сравнений.

Воспользовавшись китайской теоремой об остатках, получим ответ х = 23.

Метод Нечаева, совместно с методом Поллига-Хеллмана, позволяет свести задачу дискретного логарифмирования в общем случае к логарифмированию в подгруппе простого порядка т. При больших значениях т требование наличия объема памяти порядка у/т делает описанный нами ранее метод согласования неприменимым на практике.

Способ, который может быть применен на практике, был впервые предложен^[1] в 1978 году Джоном Поллардом (.John Pollard).

• [1] См. Pollard J.M. Monte Carlo methods for index computation (mod p) //Mathematics Of Computation. — №. 143. -Vol. 32. — 1978. -pp. 918−924.