- Алгоритм COS
-
Алгоритм COS (Копперсмит, Одлыжко, Шреппель) — субэкспоненциальный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Был предложен в 1986 году.
Содержание
Исходные данные
Пусть задано сравнение
((1)) Необходимо найти натуральное число x, удовлетворяющее сравнению (1).
Описание алгоритма
1 этап. Пусть
({{{2}}}) Сформируем множество
({{{2}}}) где q — простые.
2 этап. С помощью некоторого просеивания ищем пары — такие, что , и({{{2}}}) (рассматривается абсолютно наименьший вычет). При этом так как , то
({{{2}}}) причём это абсолютно наименьший вычет в этом классе и он имеет величину . Поэтому вероятность его гладкости выше, чем для произвольных чисел, меньших p-1.
Логарифмируя по основанию a, получим соотношение
({{{2}}}) Мы можем также считать, что a является гладким, то есть
({{{2}}}) откуда
({{{2}}})
3 этап. Набрав на 2-м этапе достаточно много уравнений, мы решим получившуюся систему линейных уравнений и найдём .4 этап. Для нахождения x введём новую границу гладкости . Случайным перебором нахоим одно значение w, удовлетворяющее соотношению
({{{2}}}) u — простые числа «средней» величины.
5 этап. С помощью методов, анаогичных этапам 2 и 3, мы находим логарифмы простых чисел u, возникших на этапе 4.
6 этап. Находим ответ:
({{{2}}}) Оценка сложности
Данный алгоритм имеет сложность арифметических операций. Предполагается, что для чисел данный алгоритм более эффективен, чем решето числового поля.
Литература
- Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 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.
Категории:- Теоретико-числовые алгоритмы
- Криптография
Wikimedia Foundation. 2010.