Алгоритм COS

Толкование

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

Содержание

1 Исходные данные

2 Описание алгоритма

3 Оценка сложности

4 Литература

Исходные данные

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

$a^x\equiv b\pmod{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.$ ({{{2}}})

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

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

где 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)}\pmod{p}$ ({{{2}}})

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

$(H+c_1)(H+c_2)\equiv J+(c_1+c_2)H+c_1c_2\pmod{p},$ ({{{2}}})

причём это абсолютно наименьший вычет в этом классе и он имеет величину $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\pmod{p-1}$ ({{{2}}})

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

$a\equiv\prod\limits_{q\leq L^{1/2}}q^{\beta_q}\pmod{p},$ ({{{2}}})

откуда

$1\equiv\sum\limits_{q\leq L^{1/2}}\beta_q\log_aq\pmod{p-1}$ ({{{2}}})

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}\pmod{p}.$ ({{{2}}})

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\pmod{p-1}.$ ({{{2}}})

Оценка сложности

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

Литература

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

Joux A., Lercier R. (2003). «Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the gaussian integer method». Math. Comp. 72: 953-967. DOI:10.1090/S0025-5718-02-01482-5.

Категории:
Теоретико-числовые алгоритмы
Криптография

Игры ⚽ Поможем сделать НИР

Полезное

Смотреть что такое "Алгоритм COS" в других словарях:

Алгоритм Шенкса — (англ. Baby step giant step; также называемый алгоритм больших и малых шагов) в теории групп, детерминированный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Для модулей специального вида данный… … Википедия
Алгоритм Фюрера — (англ. Fürer’s algorithm) быстрый метод умножения больших целых чисел. Алгоритм был построен в 2007 году швейцарским математиком Мартином Фюрером[1] из университета штата Пенсильвания как асимптотически более быстрый алгоритм, чем его… … Википедия
Алгоритм Гёрцеля — (англ. Goertzel algorithm) это специальная реализация дискретного преобразования Фурье (ДПФ) в форме рекурсивного фильтра. Данный алгоритм был предложен Джеральдом Гёрцелем в 1958 году[1]. В отличие от быстрого преобразования Фурье,… … Википедия
Алгоритм Ремеза — (также алгоритм замены Ремеза) это итеративный алгоритм равномерного аппроксимирования функций f ∊ C[a,b], основанный на теореме П. Л. Чебышёва об альтернансе. Предложен Е. Я. Ремезом в 1934 году[1]. Алгоритм Ремеза… … Википедия
Дискретное логарифмирование — (DLOG) задача обращения функции в некоторой конечной мультипликативной группе . Наиболее часто задачу дискретного логарифмирования рассматривают в мультипликативной группе кольца вычетов или конечного поля, а также в группе точек эллиптической… … Википедия
Дискретный логарифм — Дискретное логарифмирование (DLOG) – задача обращения функции gx в некоторой конечной мультипликативной группе G. Наиболее часто задачу дискетного логарифмирования рассматривают в группе обратимых элементов кольца вычетов, в мультипликативной… … Википедия
Индекс числа по модулю — Дискретное логарифмирование (DLOG) – задача обращения функции gx в некоторой конечной мультипликативной группе G. Наиболее часто задачу дискетного логарифмирования рассматривают в группе обратимых элементов кольца вычетов, в мультипликативной… … Википедия
Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и … Википедия
Программируемые алгоритмы — Служебный список статей, созданный для координации работ по развитию темы. Данное предупреждение не устанавл … Википедия
Метод квадратичных форм Шенкса — метод факторизации целых чисел, основанный на применении квадратичных форм, разработанный Даниелем Шенксом (англ. Daniel Shanks).[1] в 1975 году, как развитие метода факторизации Ферма. Для 32 разрядных компьютерах алгоритмы, основанные на… … Википедия

Словари и энциклопедии на Академике

Алгоритм COS

Содержание

Исходные данные

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

Оценка сложности

Литература

Полезное

Смотреть что такое "Алгоритм COS" в других словарях:

Поделиться ссылкой на выделенное

Словари и энциклопедии на Академике

Википедия

Алгоритм COS

Содержание

Исходные данные

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

Оценка сложности

Литература

Полезное

Смотреть что такое "Алгоритм COS" в других словарях:

Поделиться ссылкой на выделенное

Прямая ссылка: