Разрешимость задачи дискретного логарифмирования в кольцах

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

Оглавление
Обозначения
1 Введение

1.1 Разрешимость задачи дискретного логарифмирования

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

1.2.1 Разрешимость в кольце вычетов по составному модулю .

1.2.2 Разрешимость в факторкольце многочленов над конечным полем

1.2.3 О вычислении символов степенного вычета

1.3 Благодарности

2 Разрешимость показательного сравнения в кольце вычетов по составному модулю

2.1 Постановка задачи, определения, вспомогательные теоремы

2.2 Полиномиальное сведение к случаю М = pq
2.3 Разрешимость сравнения ax = b (mod pq)
2.4 Общий критерий разрешимости
3 Подъём решений показательного сравнения в факторкольце многочленов. Подъём решений показательного сравнения в цепных кольцах
3.1 Постановка задачи
3.2 Подъём решений по степени неприводимого многочлена
3.3 Подъём решений в цепных кольцах
3.4 Оптимизация алгоритма подъёма решений и проверки разрешимости

4 Разрешимость показательного сравнения по модулю произвольного многочлена над полем
4.1 Полиномиальное сведение к случаю F(x) = fi(x)fz(x)
4.2 Использование обобщённого символа Якоби (квадратичного ха-
рактера в кольце многочленов) для проверки разрешимости в частных случаях
4.3 Связь задачи дискретного логарифмирования в поле с вычислением символов степенного вычета
4.4 Разрешимость сравнения an(x) = b(x) (mod р, fi(x)f2(x)) .
4.5 Общий критерий разрешимости
5 О вычислении символов степенного вычета специального вида
5.1 Общие теоремы
5.2 Способ выбора идеалов в частных случаях
6 Заключение
Список литературы
Публикации автора по теме диссертации

Обозначения
р - простое число
Z/MZ - кольцо вычетов по модулю М (Z/MZ)* - мультипликативная группа Z/MZ огсіма - мультипликативный порядок элемента по модулю М indsa - индекс элемента а для некоторого фиксированного первообразного д (т.е. такое число, что gmd»a = a (mod р))
А(т) - функция Кармайкла Q(a, г) — ■°Л(гг)~1 (mod г) - частное Ферма (р) - символ Лежандра (Якоби) а по р Фт - круговой многочлен

= е - m-й примитивный корень из 1 К - алгебраическое расширение Q Zk - кольцо целых алгебраических поля К (-) - символ m-степенного вычета а по 7Г
7г/т
(/(f)) " обобщённый символ Якоби для многочленов GF(q) - поле характеристики р из q = р1 элементов GF(q)[х] - кольцо многочленов на полем
R = GF(q)[x]/(F(x)) - факторкольцо многочленов над полем degF^) - степень многочлена F(x)
ord^a - мультипликативный порядок элемента в кольце R Ks(a(x)) = а^(ж) - s-ый коэффициент многочлена а(х) в разложении вида
а(х) = аРх) + a^x)f{x) + a^2x)f2(x) + ... + f’/~1(x) (mod f(x))
при dega^ (x) < deg/ (x) для всех 0 < і < v —

Далее для произвольного первообразного д и идеала тт, заданного соотношением (2.11), определим функцию Сгп(д, тг) = (%)т-Поскольку
= д^ (тосі щ),

Ст(5,тг,) = а1(т0<1т) (2.12)
Сформулируем дополнительные свойства символа степенного вычета. Заметим, что данные свойства являются свойствами символов степенного вычета специального вида, а именно, они доказаны для случая, когда рассматриваемый корень из единицы (см. определение) порождает всё поле.
Лемма 4 (дополнительные свойства символа степенного вычета).
1) Ст(д,1г) является примитивным корнем из 1 степени т.
2) Пусть ді,д2 - первообразные корни по модулю р и з = ішД.рь Спг(5ъ7Г) — Ст(52)7г) тогда и только тогда, когда 5 = 1 (той т).
3) Ст(д,щ) 7^ Ст(д,ъ), где идеалы щ, ^ - различные простые делители (р).
4) Для любого е : (е, т) = 1 и любого первообразного корня д Є Z/pZ ровно один простой идеал 7г|(р). а шіепно тх — (р, £от — дДе 1), удовлетворяет условию Ст(<7) 7Г) — £т-
5) Для любого е : (е, т) — 1 и любого простого идеала тт{р) существует ровно элементов у Є таких, что (^) = Ст- При этом
(огсіру,т) = 1.
6) £ - решение сравнения аД = (дД^)1 (той р) тогда и только
тогда, когда ( — ] = £1,.
Ч^/т ТО
Доказательство:
1) Утверждение следует из представления (2.12), учитывая что (5»,ш) =

2) Предположим, Слг(зъ7Г) = Ст(