Ρ-метод Полларда дискретного логарифмирования

ρ-метод Полларда для дискретного логарифмирования — алгоритм дискретного логарифмирования в кольце вычетов по простому модулю, имеющий экспоненциальную сложность. Он был предложен Поллардом в 1978 году. Основные идеи алгоритма очень похожи на идеи ρ-метода Полларда факторизации.

Постановка задачи

Для заданного простого числа p и двух целых чисел a и b требуется найти целое число x, удовлетворяющее сравнению:

((1))

Идея алгоритма

Рассматриваются три числовые последовательности:

({{{2}}})

определённые следующим образом:

({{{2}}})

$u_{i+1} = \begin{cases} u_i+1\;\bmod\;(p-1), & 0<z_i<\frac{p}{3};\\ 2u_i\;\bmod\;(p-1), & \frac{p}{3}<z_i<\frac{2}{3}p;\\ u_i\;\bmod\;(p-1), & \frac{2}{3}p<z_i<p; \end{cases}$

({{{2}}})

$v_{i+1} = \begin{cases} v_i\;\bmod\;(p-1), & 0<z_i<\frac{p}{3};\\ 2v_i\;\bmod\;(p-1), & \frac{p}{3}<z_i<\frac{2}{3}p;\\ v_i+1\;\bmod\;(p-1), & \frac{2}{3}p<z_i<p; \end{cases}$

({{{2}}})

Замечание: везде рассматривается наименьшие неотрицательные вычеты.

Далее рассматриваются наборы и ищется номер i, для которого . Для такого i выполнено

({{{2}}})

Если при этом , то

({{{2}}})

Сложность алгоритма

Эвристическая оценка сложности составляет .

Литература

Имеется викиучебник по теме
«Программные реализации p-метода Полларда дискретного логарифмирования»

Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. — С. 328. — ISBN 5-94057-103-4

Это заготовка статьи по математике. Вы можете помочь проекту, исправив и дополнив её.

Ρ-метод Полларда дискретного логарифмирования.

Lt304888.ru

Туристические услуги

Рекомендуем

Ρ-метод Полларда дискретного логарифмирования

Содержание

Постановка задачи

Идея алгоритма

Сложность алгоритма

Литература