Подъем решений показательных уравнений в конечных кольцах

• Автор: Поповян, Илья Ардашесович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Москва
• Количество страниц: 83 с. : ил.

1 Введение

1.1 Подъём решения

1.1.1 Случай целых рациональных чисел

1.1.2 Случай целых алгебраических чисел

1.1.3 Другие группы

1.2 Результаты диссертации

1.2.1 Подъём решения

1.2.2 Оптимизация подъёма решения

2 Подъём решения

2.1 Обозначения и леммы

2.2 Теоремы о подъёме решения

2.3 Случай делителей нуля
3 Вычислительные вопросы
3.1 Вычисление логарифмов
3.1.1 Вычисление логарифма Артина-Хассе
3.1.2 Вычисление р-адического логарифма
3.2 Решение линейных сравнений
3.3 Алгоритмы подъёма решения
3.4 Оценки сложности
4 Оптимальные логарифмические функции
4.1 Оптимальные логарифмические функции
4.2 Функции и логарифм Артина-Хассе
4.3 Функции и р-адический логарифм
Литература
Глава
В современной криптографии важную роль играет понятие односторонней функции, то есть такой функции, которая вычислима за полиномиальное от длины входа время, но задача её обращения неполиномиальна. Согласно У. Диффи ([1]) в середине 70-х годов Дж. Гилл предложил использовать в качестве одностороннего отображения возведение в степень по модулю простого числа. Позже оно было обобщено до возведения в степень в произвольной конечной циклической группе, т.е. если (G, х) -циклическая группа, G =<, то
Z-+G : п^дп.
Задача обращения этого отображения называется (обобщенной) задачей дискретного логарифмирования (GDLP), а при G = (Z/(p))*, где р -простое рациональное число, эта задача называется просто задачей дискретного логарифмирования (DLP). На ее предположительной неполино-миальности основана стойкость множества асимметричных криптосхем, таких как, например, схема распределения ключей Диффи-Хэллмэна [1] или схема электронной подписи Эль-Гамаля [2] и ее варианты, DSA [3] или ГОСТ-34.10-94.
История алгоритмов для решения DLP началась, конечно, с алгоритмов, имеющих в общем случае экспоненциальную сложность, таких как “Baby-Step, Giant-Step” Шенкса [4], р- и А-методы Полларда [5], алгоритм Полига-Хэллмэна [6] и др. Одним из первых субэкспоненциальный алго-

3.3 Алгоритмы подъёма решения

Шаг 2. [Показатель] Вычислить М- := и(ао — 1) и < = |~к^р ^-]. Положить г0, т_1 := 0.
Шаг 3. [Обратный] Вычислить а?0 6 Ък по формуле
а'0 := а£‘_1(то<1 дЪк).
Шаг 4. [Логарифмы Артина-Хассе] Вычислить по формуле (3.1)
7г := Цац)(тос! цЪк),
8г Ь(Д)(тос1 дЪк).
Вычислить М* := М{-р. Если г > А — 1, перейти к шагу 8.
Шаг 5. [Линейное сравнение] Вызвать алгоритм 3.1 при
7 = 7;, 6 = &
с заменой IV на М*.
Если ответ „нет решений“, выдать ответ „нет решений“. Иначе, пусть ~ выход алгоритма 3.1, вычислить
я,- := Яг-1 + ргу',
где у- - наименьший неотрицательный вычет у* по модулю р/*.
Шаг 6. [Шаг цикла] Вычислить
счг+1 := о£(тос1 «ш := аГ(1110(1 д2я-),
Д+1 := До?*(тоё
Шаг 7. [Цикл] Положить г := г + 1, перейти к шагу 4.
Шаг 8. [Последнее линейное сравнение] Вызвать алгоритм 3.1 при
7 = 7%,8 = дг.
Если ответ „нет решений“, выдать ответ „нет решений“. Иначе, пусть (/;, у 1) - выход алгоритма 3.1, вычислить
Хг := Хг-1 +р%