- Ρ-метод Полларда дискретного логарифмирования
-
ρ-метод Полларда для дискретного логарифмирования — алгоритм дискретного логарифмирования в кольце вычетов по простому модулю, имеющий экспоненциальную сложность. Он был предложен Поллардом в 1978 году. Основные идеи алгоритма очень похожи на идеи ρ-метода Полларда факторизации.
Содержание
Постановка задачи
Для заданного простого числа p и двух целых чисел a и b требуется найти целое число x, удовлетворяющее сравнению:
((1)) Идея алгоритма
Рассматриваются три числовые последовательности:
({{{2}}}) определённые следующим образом:
({{{2}}})
({{{2}}})
({{{2}}})
({{{2}}}) Замечание: везде рассматривается наименьшие неотрицательные вычеты.
Далее рассматриваются наборы и ищется номер i, для которого . Для такого i выполнено
({{{2}}}) Если при этом , то
({{{2}}}) Сложность алгоритма
Эвристическая оценка сложности составляет .
Литература
- Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. — С. 328. — ISBN 5-94057-103-4
Категория:- Теоретико-числовые алгоритмы
Wikimedia Foundation. 2010.