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

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

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

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

$a^x\equiv b\;\pmod{p}.$

((1))

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

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

$\{u_i\}, \{v_i\}, \{z_i\},\ i\in N,$

({{{2}}})

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

$u_0=v_0=0,\ z_0=1;$

({{{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}}})

$z_{i+1}\equiv b^{u_{i+1}}a^{v_{i+1}}\pmod{p-1}.$

({{{2}}})

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

Далее рассматриваются наборы $(z_i,\ u_i,\ v_i,\ z_{2i},\ u_{2i},\ v_{2i})$ и ищется номер i, для которого $z_i = z_{2i}$. Для такого i выполнено

$b^{u_{2i}-u_i}\equiv a^{v_{i}-v_{2i}} \pmod{p}.$

({{{2}}})

Если при этом $(u_{2i}-u_i,\ p-1)=1$, то

$x\equiv\log_a{b}\equiv(u_{2i}-u_i)^{-1}(v_{i}-v_{2i})\pmod{p-1}.$

({{{2}}})

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

Эвристическая оценка сложности составляет $O(p^{\frac{1}{2}})$.

Литература

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