Фэндом


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


Исходные данныеПравить

Пусть задано сравнение

a^x\equiv b\mod{p}. (1)

Необходимо найти натуральное число x, удовлетворяющее сравнению (1).

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

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

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

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

u_0=v_0=0,\ z_0=1;


u_{i+1}\equiv\left\{\begin{matrix}
u_i+1 & \mod{p-1}, & 0<z_i<\frac{p}{3};\\
2u_i & \mod{p-1}, & \frac{p}{3}<z_i<\frac{2}{3}p;\\
u_i & \mod{p-1}, & \frac{2}{3}p<z_i<p;
\end{matrix}\right.


v_{i+1}\equiv\left\{\begin{matrix}
v_i & \mod{p-1}, &  0<z_i<\frac{p}{3};\\
2v_i & \mod{p-1}, & \frac{p}{3}<z_i<\frac{2}{3}p;\\
v_i+1 & \mod{p-1}, & \frac{2}{3}p<z_i<p;
\end{matrix}\right.


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

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

Далее рассматриваются наборы (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}} \mod{p}.

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

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

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

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

ЛитератураПравить

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


Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

Также на Фэндоме

Случайная вики