Викия

Математика

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

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Share

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


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

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

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


Викия-сеть

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