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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

ρ-метод Полларда для дискретного логарифмирования — алгоритм дискретного логарифмирования в кольце вычетов по простому модулю, имеющий экспоненциальную сложность. Он был предложен Поллардом в 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}}).

Литература[править | править исходный текст]