Алгоритм COS: различия между версиями
[отпатрулированная версия] | [непроверенная версия] |
Maxal (обсуждение | вклад) →Литература: оформление |
Нет описания правки |
||
Строка 1: | Строка 1: | ||
'''Алгоритм COS''' (Копперсмит, Одлыжко, Шреппель) |
'''Алгоритм COS''' (Копперсмит, Одлыжко, Шреппель) — субэкспоненциальный алгоритм [[дискретное логарифмирование|дискретного логарифмирования]] в [[сравнение по модулю натурального числа|кольце вычетов]] по модулю простого числа. Был предложен в [[1986 год]]у. |
||
==Исходные данные== |
== Исходные данные == |
||
Пусть задано сравнение |
Пусть задано сравнение |
||
{{Формула |
{{Формула |
||
|<math>a^x\equiv b\mod{p},</math>|(1)}} |
|<math>a^x\equiv b\mod{p},</math>|(1)}} |
||
Строка 9: | Строка 9: | ||
Необходимо найти натуральное число ''x'', удовлетворяющее сравнению (1). |
Необходимо найти натуральное число ''x'', удовлетворяющее сравнению (1). |
||
==Описание алгоритма== |
== Описание алгоритма == |
||
'''1 этап.''' Пусть |
'''1 этап.''' Пусть |
||
Строка 19: | Строка 19: | ||
|<math>\{q\mid q<L^{1/2}\}\cup\{H+c|0<c<L^{1/2+\epsilon}\},</math>}} |
|<math>\{q\mid q<L^{1/2}\}\cup\{H+c|0<c<L^{1/2+\epsilon}\},</math>}} |
||
где ''q'' |
где ''q'' — простые. |
||
'''2 этап.''' С помощью некоторого просеивания ищем пары <math>c_1,\ c_2</math> |
'''2 этап.''' С помощью некоторого просеивания ищем пары <math>c_1,\ c_2</math> — такие, что <math>0<c_i<L^{1/2+\epsilon}</math>, и |
||
{{Формула |
{{Формула |
||
Строка 32: | Строка 32: | ||
|<math>(H+c_1)(H+c_2)\equiv J+(c_1+c_2)H+c_1c_2\mod{p},</math>}} |
|<math>(H+c_1)(H+c_2)\equiv J+(c_1+c_2)H+c_1c_2\mod{p},</math>}} |
||
причём это абсолютно наименьший вычет в этом классе и он имеет величину <math>O(p^{1/2+\epsilon})</math>. Поэтому вероятность его гладкости выше, чем для произвольных чисел, меньших ''p-1''. |
причём это абсолютно наименьший вычет в этом классе и он имеет величину <math>O(p^{1/2+\epsilon})</math>. Поэтому вероятность его гладкости выше, чем для произвольных чисел, меньших ''p-1''. |
||
Логарифмируя по основанию ''a'', получим соотношение |
Логарифмируя по основанию ''a'', получим соотношение |
||
Строка 38: | Строка 38: | ||
|<math>\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}</math>}} |
|<math>\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}</math>}} |
||
Мы можем также считать, что ''a'' является гладким, то есть |
Мы можем также считать, что ''a'' является гладким, то есть |
||
{{Формула |
{{Формула |
||
|<math>a\equiv\prod\limits_{q\leq L^{1/2}}q^{\beta_q}\mod{p},</math>}} |
|<math>a\equiv\prod\limits_{q\leq L^{1/2}}q^{\beta_q}\mod{p},</math>}} |
||
Строка 52: | Строка 52: | ||
|<math>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}.</math>}} |
|<math>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}.</math>}} |
||
''u'' |
''u'' — простые числа «средней» величины. |
||
'''5 этап.''' С помощью методов, анаогичных этапам 2 и 3, мы находим логарифмы простых чисел ''u'', возникших на этапе 4. |
'''5 этап.''' С помощью методов, анаогичных этапам 2 и 3, мы находим логарифмы простых чисел ''u'', возникших на этапе 4. |
||
Строка 60: | Строка 60: | ||
|<math>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}.</math>}} |
|<math>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}.</math>}} |
||
==Оценка сложности== |
== Оценка сложности == |
||
Данный алгоритм имеет сложность <math>O(\exp{((\log{p}\log{\log{p}})^{1/2})})</math> арифметических операций. Предполагается, что для чисел <math>p<10^{90}</math> данный алгоритм более эффективен, чем решето числового поля. |
Данный алгоритм имеет сложность <math>O(\exp{((\log{p}\log{\log{p}})^{1/2})})</math> арифметических операций. Предполагается, что для чисел <math>p<10^{90}</math> данный алгоритм более эффективен, чем решето числового поля. |
||
==Литература== |
== Литература == |
||
* {{книга |
* {{книга |
Версия от 06:14, 20 декабря 2009
Алгоритм COS (Копперсмит, Одлыжко, Шреппель) — субэкспоненциальный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Был предложен в 1986 году.
Исходные данные
Пусть задано сравнение
((1)) |
Необходимо найти натуральное число x, удовлетворяющее сравнению (1).
Описание алгоритма
1 этап. Пусть
Сформируем множество
где q — простые.
2 этап. С помощью некоторого просеивания ищем пары — такие, что , и
(рассматривается абсолютно наименьший вычет). При этом так как , то
причём это абсолютно наименьший вычет в этом классе и он имеет величину . Поэтому вероятность его гладкости выше, чем для произвольных чисел, меньших p-1.
Логарифмируя по основанию a, получим соотношение
Мы можем также считать, что a является гладким, то есть
откуда
3 этап. Набрав на 2-м этапе достаточно много уравнений, мы решим получившуюся систему линейных уравнений и найдём .
4 этап. Для нахождения x введём новую границу гладкости . Случайным перебором нахоим одно значение w, удовлетворяющее соотношению
u — простые числа «средней» величины.
5 этап. С помощью методов, анаогичных этапам 2 и 3, мы находим логарифмы простых чисел u, возникших на этапе 4.
6 этап. Находим ответ:
Оценка сложности
Данный алгоритм имеет сложность арифметических операций. Предполагается, что для чисел данный алгоритм более эффективен, чем решето числового поля.
Литература
- Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 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.
Это заготовка статьи по математике. Помогите Википедии, дополнив её. |