Викия

Математика

Алгоритм COS

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

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


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

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

Алгоритм COS (Копперсмит, Одлыжко, Шреппель) – субэкспоненциальный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Был предложен в 1986 году.

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

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

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

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

Описание алгоритмаПравить

1 этап. Пусть

H:=[p^{1/2}]+1,\  J:=H^2-p>0,\ L=e^{\sqrt{\log{p}\log{\log{p}}}},\ 0<\epsilon<1.

Сформируем множество

\{q\mid q<L^{1/2}\}\cup\{H+c|0<c<L^{1/2+\epsilon}\},

где q – простые.


2 этап. С помощью некоторого просеивания ищем пары c_1,\ c_2 - такие, что 0<c_i<L^{1/2+\epsilon}, и

(H+c_1)(H+c_2)\equiv\prod\limits_{q\leq L^{1/2}}q^{\alpha_q(c_1,c_2)}\mod{p}

(рассматривается абсолютно наименьший вычет). При этом так как J=O(p^{1/2}), то

(H+c_1)(H+c_2)\equiv J+(c_1+c_2)H+c_1c_2\mod{p},

причём это абсолютно наименьший вычет в этом классе и он имеет величину O(p^{1/2+\epsilon}). Поэтому вероятность его гладкости выше, чем для произвольных чисел, меньших p-1.

Логарифмируя по основанию a, получим соотношение

\log_a{(H+c_1)}+\log_a{(H+c_2)}\equiv\sum\limits_{q\leq L^{1/2}}\alpha_q(c_1,c_2)\log_aq\mod{p-1}

Мы можем также считать, что a является гладким, то есть

a\equiv\prod\limits_{q\leq L^{1/2}}q^{\beta_q}\mod{p},

откуда

1\equiv\sum\limits_{q\leq L^{1/2}}\beta_q\log_aq\mod{p-1}


3 этап. Набрав на 2-м этапе достаточно много уравнений, мы решим получившуюся систему линейных уравнений и найдём \log_a{(H+c)}, \ \log_aq.

4 этап. Для нахождения x введём новую границу гладкости L^2. Случайным перебором нахоим одно значение w, удовлетворяющее соотношению

a^wb\equiv\prod{q\leq L^{1/2}}q^{\gamma_q}\prod\limits_{L^{1/2}\leq u<L^2}u^{h_u}\mod{p}.

u – простые числа "средней" величины.

5 этап. С помощью методов, анаогичных этапам 2 и 3, мы находим логарифмы простых чисел u, возникших на этапе 4.

6 этап. Находим ответ:

x\equiv\log_ab\equiv-w+\sum{q\leq L^{1/2}}\gamma_q\log_aq +  \sum\limits_{L^{1/2}\leq u<L^2}h_u\log_au\mod{p-1}.

Оценка сложностиПравить

Данный алгоритм имеет сложность O(\exp{((\log{p}\log{\log{p}})^{1/2})}) арифметических операций. Предполагается, что для чисел p<10^{90} данный алгоритм более эффективен, чем решето числового поля.

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

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


Викия-сеть

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