Содержание к диссертации
1 Введение 4
1.1 Подъём решения 5
Случай целых рациональных чисел 5
Случай целых алгебраических чисел 10
Другие группы 11
1.2 Результаты диссертации 12
Подъём решения 12
Оптимизация подъёма решения 16
2 Подъём решения 21
Обозначения и леммы 21
Теоремы о подъёме решения 30
Случай делителей нуля 35
3 Вычислительные вопросы 37
3.1 Вычисление логарифмов 37
Вычисление логарифма Артина-Хассе 37
Вычисление р-адического логарифма 38
Решение линейных сравнений 42
Алгоритмы подъёма решения 48
Оценки сложности 56
4 Оптимальные логарифмические функции 66
Оптимальные логарифмические функции 66
Функции QS!^p и логарифм Артина-Хассе 71
4.3 Функции Qs>nM и р-адический логарифм 75
Литература 80
Введение к работе
В современной криптографии важную роль играет понятие односторонней функции, то есть такой функции, которая вычислима за полиномиальное от длины входа время, но задача её обращения неполиномиальна. Согласно У. Диффи ([1]) в середине 70-х годов Дж. Гилл предложил использовать в качестве одностороннего отображения возведение в степень по модулю простого числа. Позже оно было обобщено до возведения в степень в произвольной конечной циклической группе, т.е. если (G, х) -циклическая группа, G =<д>, то
Z-+G : п^дп.
Задача обращения этого отображения называется (обобщенной) задачей дискретного логарифмирования (GDLP), а при G = (Z/(p))*, где р -простое рациональное число, эта задача называется просто задачей дискретного логарифмирования (DLP). На ее предположительной неполино-миальности основана стойкость множества асимметричных криптосхем, таких как, например, схема распределения ключей Диффи-Хэллмэна [1] или схема электронной подписи Эль-Гамаля [2] и ее варианты, DS А [3] или ГОСТ-34.10-94.
История алгоритмов для решения DLP началась, конечно, с алгоритмов, имеющих в общем случае экспоненциальную сложность, таких как "Baby-Step, Giant-Step" Шенкса [4], р- и А-методы Лолларда [5], алгоритм Полига-Хэллмэна [6] и др. Одним из первых субэкспоненциальный алго-
