Разрешимость задачи дискретного логарифмирования в кольцах тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

Московский Государственный Университет

_имени М.В. Ломоносова_

Механико-математический факультет

Маркелова Александра Викторовна.

РАЗРЕШИМОСТЬ ЗАДАЧИ ДИСКРЕТНОГО ЛОГАРИФМИРОВАНИЯ В КОЛЬЦАХ

Специальность 01.01.06 - математическая логика, алгебра и теория чисе.,

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

О 3 [-1\? 2011

Москва, 2011

4856566

Работа выполнена на кафедре теории чисел Механико-математического факультета Московского государственного университета имени М.В. Ломоносова.

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

кандидат физико-математических наук, доцент Михаил Алексеевич Черепнёв доктор физико-математических наук, профессор Владимир Григорьевич Чирский кандидат физико-математических наук Вадим Владиславович Назаров Институт информационных наук и технологий безопасности (ИИНТБ) РГГУ

Защита диссертации состоится И марта 2011 г. в 16 ч. 45 м.на заседании диссертационного совета Д.501.001.84 при Московском государственном университете имени М.В. Ломоносова по адресу: Российская Федерация, 119991, ГСП-1, Москва, Ленинские горы, д. 1, МГУ, Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета Московского государственного университета имени М.В. Ломоносова (Главное здание, 14 этаж).

Автореферат разослан 11 февраля 2011 г.

Ученый секретарь диссертационного совета Д.501.001.84 при МГУ доктор физико-математических наук, профессор

А.О.Иванов

Общая характеристика работы

Актуальность темы

Задача дискретного логарифмирования является одной из ключевых задач современной теории чисел. Вопрос дискретного логарифмирования в конечных кольцах зачастую полиномиально сводится к дискретному логарифмированию в конечных полях. Но в случае, если мультипликативная группа кольца не является циклической, возникает дополнительный вопрос: вопрос о существовании решения' показательного сравнения.

Buchmann J., Jacobson M.J., Teske E.1 приводят алгоритм для проверки разрешимости в произвольной абелевой группе. Данный алгоритм для конечной мультипликативной абелевой группы G и элементов а, ß 6 G за 0(^/((а)|) умножений проверяет, принадлежит ли элемент ß циклической группе (а), порождённой элементом а, и в случае положительного ответа находит logaJö. Для проверки используется таблица, состоящая из 0(у/|(а)|) пар элементов.

Данный алгоритм малоинтересен, поскольку имеет слишком большую сложность. Естественно ожидать, что при рассмотрении задачи не в произвольной группе, а в мультипликативной группе некоторого конкретного конечного кольца, структура которого нам хорошо известна, сложность окажется существенно меньше.

Этой темой занимался О.Н.Василенко. Он рассматривал вопрос о разрешимости показательного сравнения в кольце вычетов по составному модулю2 и в факторкольце многочленов над конечным полем3. Им были получены некоторые критерии разрешимости для частных случаев.

Прежде всего, рассмотрим задачу дискретного логарифмирования в кольце вычетов по составному модулю. О.Н.Василенко сформулировал и доказал

1Buchmann J., Jacobson M.J., Teske E. On some computational problems in finite abelian groups. Mathematics of Computation, 1997, V. 66 (220), p. 1663-1687.

2Василснко O.H. О разрешимости задачи дискретного логарифмирования в кольцах вычетов. Фунд. и прикл. матем, 2002. 8, № 3. 647-653.

'Василенко О.Н. О дискретном логарифмировании в некоторых группах. Вестник МГУ, сер.1. Матеы. Метал., 2000, №5, с. 53-55.

теорему2, позволяющую проверять разрешимость показательного сравнения

ах = Ь (mod M)

для M = pi ■ ... • pk, где все pi - различные нечётные простые, имеющие специальный вид, при условии, что порядок а по модулям pi строго равен одному из двух значений pi — 1 или

Далее, интерес представляет вопрос о разрешимости показательного сравнения в факторкольце многочленов над полем. Cohen H., Dyaz у Dyaz F., Olyver M. в 1998 году4, затем Hess F., Pauli S., Pohst M.E. в 2003 году5 и позднее Поповян И.А. в 2006 году6 рассматривали задачу подъёма решений показательного сравнения в кольце целых алгебраических чисел. Было доказано, что решение сравнения

ax = ß (mod тг")

для некоторых а, ß € Zu и простого идеала тг полиномиально сводится к нахождению решения сравнения

ах = ß (mod тг).

Такое сведение осуществлялось при помощи различных логарифмических функций, а именно частных Ферма специального вида, р-адических логарифмов и логарифмов Артина-Хассе.

Частным случаем рассматриваемой задачи является сравнение вида

ап(х)=Ъ(х) (mod p",f(x)),

где многочлен f(x) со старшим коэффициентом 1 неприводим по модулю простого р.

При этом решение задачи сводится к нахождению решения сравнения ап(х) = b(x) (mod р, f(x)).

4Cohen H., Diaz y Diaz F., Oliver M. Computing ray class groups, conductors and discriminants. Math, Сотр., Vol. 67:222, 1998, pp. 773-795.

5Hess F., Pauli S., Pohst M.E. Computing the multiplicative group of residue class rings. Matk. Сотр., Vol. 72:243, 2003, pp. 1531-1548.

8Поповян И.А. Подъём решений показательного сравнения. Математические заметки, 2006, 80:1, с.76-86

Однако, решение последнего сравнения можно "поднимать" не только по степеням р, но и по степеням f(x). Вопрос о подъёме решений сравнения

fl"(x) = fc(z) (mod р, Г(Х)) {1)

рассматривался О.Н.Василенко3, и им были получены некоторые результаты для случая р/2 < v < р, orda(z) = рд\, ordb(z) = р62, ^l^'ili^ ~ 1 (d = deg/(x)) при условии, что Ф 0 (mod p,f(x)). А именно, при

данных ограничениях и в случае разрешимости сравнения (1) были получены формулы для подъёма решений этого сравнения.

Цель работы

Цель диссертации - получение конструктивных критериев разрешимости задачи дискретного логарифмирования в кольцах вычетов по произвольному составному модулю и в факторкольцах многочленов над конечными полями, подъём решений показательного сравнения в факторкольцах многочленов над конечными полями по степени неприводимого многочлена, оптимизация вычислительной сложности полученных алгоритмов.

Научная новизна

Результаты диссертации являются новыми и состоят в следующем:

• Получен критерий разрешимости показательного сравнения в кольце вычетов по модулю составного числа. Доказано, что вопрос о разрешимости показательного сравнения по модулю произвольного составного числа полиномиально сводится к вычислению символов степенного вычета с некоторыми простыми индексами, являющимися делителями р—1, гдер\М. Приведён конструктивный полиномиальный алгоритм такого сведения. Итоговая теорема обобщает полученные О.Н.Василенко критерии.

• Решена задача подъёма решений по модулю степени неприводимого многочлена над конечным полем. Приведён алгоритм её полиномиального сведения к аналогичной задаче по модулю самого неприводимого многочлена. Итоговая теорема обобщает критерии О.Н.Василенко.

• Решена задача подъёма решений показательного сравнения в цепных кольцах. Описаны возможные оптимизации алгоритма подъёма решений по модулю степени неприводимого многочлена над конечным полем при помощи построения конструктивных изоморфизмов в цепные кольца. Получены оценки сложности предлагаемых модификаций.

• Получен критерий разрешимости показательного сравнения по модулю произвольного многочлена над конечным полем. Доказано, что вопрос о разрешимости полиномиально сводится к вычислению символов степенного вычета.

• Получены формулы для "подъёма" символа степенного вычета в ряде случаев, используемых в доказанных выше критериях разрешимости. А именно, показано, что в случае, когда - 1, вычисление символа степени гк полиномиально сводится к вычислению символов степени г, где г - простое.

Основные методы исследования

В диссертации используются методы алгебраической теории чисел, теории конечных колец, теории сложности вычислений.

Теоретическая и практическая ценность

В диссертации доказываются теоремы и выводятся формулы, которые могут найти применение в алгебраической теории чисел. Построенные алгоритмы с оценками сложности могут использоваться в вычислительной теории чисел.

Апробация работы

Результаты диссертации докладывались автором на следующих научных семинарах и конференциях:

• на научно-исследовательском семинаре по теории чисел под руководством проф. Ю.В.Нестеренко, проф. Н.Г.Мощевитина (2008 г., 2010 г.);

• на семинаре "Теоретико-числовые вопросы криптографии" под руководством доц. М.А.Черепнёва (2008 г., 2009 г., 2010 г.);

• на конференции "Ломоносовские чтения" (Москва, 2009 г.);

• на конференции "Математика и безопасность информационных технологий" (Москва, 2004 г., 2009 г., 2010 г.).

Публикации

Результаты автора по теме диссертации опубликованы в 3 работах, список которых приводится в конце автореферата [1-3].

Структура и объём диссертации

Диссертация состоит из введения, четырёх глав, заключения и библиографии (37 наименований). Общий объём диссертации составляет 89 страниц.

Содержание работы

Во введении, являющемся первой главой, описывается структура диссертации, обосновывается актуальность темы и научная новизна полученных результатов, излагаются основные результаты диссертации.

Во второй главе сформулирован и доказан критерий разрешимости сравнения

ах = Ь (mod М), (2)

где М — Pi1 •... • plk, Pi - различные простые, щ € N, а, Ь € (Z/MZ)*.

Для случая к = 1 разрешимость проверяется с использованием частных Ферма Q(a,r) = (mod г) по следующим теоремам.

Теорема 1. Для М = pv, где р - простое, нечётное, v > 1, сравнение (2) равносильно системе

Q{ayl)x = Q{b,pv~l) (mod р^1), ах = b (mod р).

Теорема 2. Для М = > 5 сравнение (2) равносильно системе

Q(a,2"~2)x = g(6,2"-2) (mod 2l"2), ax = b (mod 4).

Данные теоремы широко7,8,9 известны для случая, когда а - первообразный по модулю простого нечётного р или а = 5 при р — 2. Однако, они верны и для произвольного а. Эти теоремы полезны не только для проверки разрешимости, но и для подъёма решений показательного сравнения. Решения линейных сравнений приведённых выше систем будут использоваться в следующей теореме.

Теорема 3. Пусть к > 2 и ord^a = Si — {Pj,öij) = 1 для всех

пар (i,j). Обозначим через Cj решение сравнения ах b (modp^) по модулю Si, а через 5 - его вычет по модулю Сравнение (2) разрешимо тогда и только тогда, когда выполнены следующие условия:

1) при щ > 1 сравнение ах = b (mod рразрешимо;

2) при любых j сравнение ах = & (mod PiPj) разрешимо;

~ С maxiMjj-^jj-.O}

3) если Vj > 1 и pij > 0, то {ba~c>)' iiP> = 1 (mod pi).

В результате исходная задача редуцируется к случаю, когда к = 2, р\,р2 - нечётные, ^ = jy2 = 1.

Далее в главе 2 сформулирован следующий критерий разрешимости показательного сравнения по модулю pq для некоторых частных случаев.

Лемма 3. Пусть р = 2r + 1, q = 2s + 1, где (г, s) = 1, г и s - нечётные. Сравнение

ах = Ь (mod pq)

разрешимо тогда и только тогда, когда:

1) ах = 6 разрешимо по модулям р и q;

Совокупность данной леммы и теоремы 3 даёт обобщение результатов О.Н.Василенко2. В частности, можно отказаться от условия щ — 1, снять ограничения на чётность М и на значения ordPia.

В лемме 3 для проверки разрешимости используется символ Лежандра. Для обобщения результатов на случай произвольных р и q нам потребуется

'Riesel Н. Some soluble cases of the discrete logarithm problem. BIT, v28, no4, 1988.

8Нестеренко Ю.В., Частные Ферма и р-адические логарифмы. Труды по дискретной математике, т. 5, М. "Физматлит", 2002, с. 173-188.

9Василснко О.Н. Теоретико-числовые алгоритмы в криптографии. М.-. МЦНМО, 2003.

обобщение символа Лежандра - символ степенного вычета.

Здесь приводится определение в соответствии с Artin Е., Tate J.10.

Пусть задано поле К, являющееся конечным расширением Q, простой идеал 7г в его кольце целых Zr, целое число т £ тг, и пусть К содержит m-ый корень из единицы При этом т | Niг — 1. Для целого алгебраического а определим символ степенного вычета следующим образом:

— ] = = q^^1 (mod 7г), если а 0 тг;

nJm

( - ) ~ 0, если о 6 7Г.

Wm

Данный символ является обобщением символа Лежандра и обладает аналогичными свойствами: периодичностью и мультипликативностью.

Пусть далее р - 1 = г"1^2 • ... • rf* • р', q - 1 = rf'rj2 • ... • rf* • <j', где все rj - различные простые и (р\г*) = (q1, fj) = (р',?') — 1. Пусть заданы разложения на простые идеалы в кольцах целых алгебраических:

(р) = тгдтг^ ■ • • в

(?) = ■ • • в

ч

Обозначим 7fj = 7Гд И Pj = Pyi.

$ s

Пусть ordpa = Д r]1J6i, ord„a = П где 0 < 7у < а,, 0 < 72j < j=i j=i ¿ijp', ¿г!?'- При этом

атд^'^д^'11 (modp),

a ^ gf'" = (mod q)

для некоторых первообразных g\, <72- Причём (ry, sjj) = (rj, S2j) = 1-

Тогда для любого j при jy ф 0 и 72j ф 0 однозначно определяются такие ец и e2j, что 0 < < r]lj, 0 < e2j < r]*j, что (ец,г,) = (e2j,rj) = 1 и

, -«■Г*,

Vft/rf' V

10 Art in E., Tate J. Class Field Theory. 1968, W.A.Benjamin, Inc.

При 7ij = 0 (j2j = 0) считаем ец — 1 (e2j = 1).

Для вычисления чисел ец, e^j необходимо и достаточно вычислить символы степенного вычета для а.

В этих обозначениях можно сформулировать следующую теорему, дающую критерий разрешимости показательного сравнения по модулю рд. Теорема 6. Сравнение

ах = b (mod pq)

разрешимо в том и только том случае, когда ах = Ь разрешимо по модулям р и q, и для всех j выполнено: - если 72j > 7ц, то

b у Г/ (mod rj") , b у?-*-eg (mod г??

^jJrV \Рз)г1>

= 0;

- иначе a

PiJ/j \

b \ <mod rT') ( b \ (inod >

Совокупность теорем 3 и 6 даёт общий критерий разрешимости показательного сравнения в кольце вычетов.

В третьей главе диссертации рассматривается показательное сравнение в кольце R = GF(q)[x]/(f(x)), где q = р1, р - простое число, I € N, и € 1}, а многочлен f(x) неприводим над GF(q)[x], имеет старший коэффициент 1 и deg f(x) — d.

R является кольцом с однозначным разложением на простые множители11, и каждый элемент кольца R можно однозначно представить в виде:

а(х) = аЩх) + a®(x)f(x) + ... + а^{х)Г'1{х) (mod /"(®)), dega'''(a;) < d.

Обозначим Ks{a{x)) = а^(х) - s-ый коэффициент в этом разложении. Положим по определению Ки(а(х)) = 0.

11Вал дер Варден Б. Л. Алгебра. Наука, Москва, 1976.

Если ord^u(x) = jt", to u(x) = 1 (mod f(x)). Таким образом, корректно определить следующую функцию:

D : fD{x)\\u{x) - 1, при и{х) ^ 1 (mod /"(я)); и, при и(х) = 1 (mod /"( х)).

Функция K£>u(aq<1-i(x)){aqd~l{x)) фактически является аналогом частного Ферма в рассматриваемом факторкольце многочленов. С её помощью сформулирована и доказана теорема о подъёме решений в факторкольце по степени неприводимого многочлена над произвольным конечным полем.

Теорема 9 (о подъёме решений). Сравнение

ап(х) = Ь{х) (mod f{x)) над полем GF(q) равносильно системе:

' ап(х) = Ъ(х) (mod /(я)); при i б {0,..., м - 1} s(i) = Dv(a,(qd~l)pi (х)); < mKm(a«-W(x)) =

(mod /(ж));

п = по + щр +... -г п^-ip^-1 (mod р11); _ ап^~1\х) = Ь^{х) (mod f(x)).

где ordfla(x) = р^5, 5\qd — 1.

Используя теорему 9, нетрудно построить конструктивный полиномиальный алгоритм подъёма решений и проверки разрешимости в кольце R, сложность которого при I = 1 составляет 0(dulog(di')(d + log log р) арифметических операций в поле GF{p), а при I > 1 равна 0{ldv logl\og(di>)(dl + logz/) log p) арифметических операций в поле GF(p). Кроме того, поскольку кольцо R является цепным, то можно построить конструктивный изоморфизм из R в Л = GF(pr)[x]/(х1) (при r — ld,t = и), что позволяет в некоторых случаях оптимизировать алгоритм проверки разрешимости и подъёма решений.

В четвёртой главе сформулирован и доказан критерий разрешимости задачи дискретного логарифмирования в факторкольце по произвольному составному многочлену над полем GF{q), q =pl.

Dv(u(x))

Как и в случае кольца вычетов, вначале получена теорема, сводящая проверку разрешимости по модулю произвольного приводимого многочлена к аналогичной задаче по модулю произведения двух различных неприводимых многочленов.

Теорема 11. Пусть F{x) = /Р(х) •... ■ flk{x), где все ft - различные неприводимые над полем GF(q), со старшими коэффициентами 1, k > 1, ordр^а(х) = Si = где (р,6[) = 1. Обозначим через щ решение сравнения ап(х) = b(x) (mod fi'{x)), а черезщ его вычет по модулюрСравнение

ап(х) = b(x) (mod F(x))

разрешимо тогда и только тогда, когда выполнены следующие условия: 1) Vz сравнение ап(х) = b(x) (mod fffa)) разрешимо; Ю W Ф 3 сравнение ап(х) = b(x) (mod fi(x)fj{x)) разрешимо; 3) щ = щ (mod jr**^)).

Отдельно в главе 4 рассмотрен частный случай задачи, использующий обобщение символа Якоби для многочленов, поскольку этот случай является наиболее простым с вычислительной точки зрения.

Если f(x) - неприводимый многочлен со старшим коэффициентом 1, то обобщённый символ Якоби определяется следующим образом12:

\т)

1, если (¡(х),д(х)) = 1 и

д(х) - квадрат по модулю /(ж); -1, если (¡(х),д(х)) = 1 и

д(х) - не квадрат по модулю /(ж); О, иначе.

Если /(х) = Д(х) • ... ■ ¡Г{х), где /¿(х) - неприводимые, со старшими коэффициентами 1, то обобщённый символ Якоби определяется по мультипликативности:

( = и (9^ХЛ \№) Ц \№))"

Обобщённый символ Якоби обладает стандартными свойствами: мультипликативностью и периодичностью. Полиномиальный алгоритм вычисления

12Bach Е., Shallit J. Algorithmic number theory. V. 1. MIT Press, Massachusetts, 1996.

обобщённого символа Якоби12 для произвольных многочленов f(x) и д(х) использует закон взаимности, а также квадратичный характер в поле GF(q)

(X(c) = cV).

Лемма 9. Пусть р - нечётное простое, deg/j(x) = d\, degf2(x) — d2l pidi —2r + l, pldi = 2s + 1, где (r,s) = 1, г и s - нечётные. Сравнение

an(x) = b(x) (mod h(x)f2(x))

разрешимо тогда и только тогда, когда

1) ап(х) = Ь(х) разрешимо по модулям fi{x) и /2(3);

Например, данная лемма применима для произвольного а(х) в случае, если р — 3,1 = 1, {d\,d2) = 1, di - нечётные.

Далее будем рассматривать задачу только над простым полем и обобщим лемму 9 на произвольный случай.

Пусть deg/i(®) = dh degf2{x) = d2,pd>-1 = 1 = г?'...rf-pi,

где rj - различные простые и (р^г*) = (р'2,тч) = (р'црг) = 1-

Для всех j (1 < j < s) и i = 1,2 введём следующие обозначения: ¡г,- -корень /¡(ж), Q(<rb£ -j) = Q(cr2,^ = K2j, ZKy - кольцо целых в Щ, (Р) = 7Tji7Tj2... - разложение на простые в Zкц> 7Tj = 7Tji, (р) = pjipj2... -разложение на простые в Zk2j , Pj = pji-

Пусть далее ord/l(:c)a(:r) = rJ'My, ord/2(:r)a(:r) = r]vd2j, где 0 < ту < a,-, О < 72j < Pj, (rj, Sij) = (rj, 62j) = 1. При этом для некоторых порождающих элементов <?i(x) (mod fi(x)) и дг(^) (mod f2(x)) выполнено

а(х) ~ = giixp^11^ (mod р, Мх)),

а(х) = g2(x)^^S2 s g2(xpj'12is* (mod р, /2(®)),

где (г,, sij) = (fj, s2j) = 1 для всех j (1 < j < s).

Тогда для любого j при 71 j ф 0 и 72j ф 0 однозначно определяются такие О < ец < г]1*, 0 < e2j < rfj, что (ey.rj) = (еу, г,-) = 1 и

При 7ij = 0 (72j = 0) считаем еу = 1 (e2j = 1).

Для нахождения чисел е^ необходимо и достаточно вычислить символы степенного вычета для a[ai). Теорема 14. Сравнение

ап{х) = Ъ(х) (mod р, fi(x)f2{x))

разрешимо тогда и только тогда, когда разрешимы аналогичные сравнения по модулям fi(x) и h(x) и для всех j (\ < j < s) выполнено:

- если 72; > 7ij, то

((а±А) _ Л. (mod r?J) _ fаду^^1 (mod ^

\v щ )r? / \V ^ ЛV pi )r'>

- иначе

ff^l) _Л. f(b^rf^'(mod_ (Mf(mod

\v Pi ) ^v щ ) ^ v PÙ

Таким образом, совокупность теорем 11 и 14 даёт критерий разрешимости показательного сравнения в произвольном факторкольце многочленов над конечным полем.

Вопрос о разрешимости показательного сравнения, как в случае кольца вычетов по составному модулю, так и в случае факторкольца многочленов, свёлся к вычислению символов степенного вычета. Полученные критерии являются конструктивными, только если вычисление соответствующих символов можно выполнить за полиномиальное время. Изучению этого вопроса посвящена пятая глава диссертации.

На данный момент вопрос о быстром вычислении r-степенного символа (для простого г) в общем случае остаётся открытым. Хорошо известен способ вычисления символа Лежандра (т.е. при г = 2). Scheidler R.13 (глава 7) описывает алгоритмы вычисления символов степенного вычета для г — 3, 5. В 2009 году аналогичный алгоритм, использующий обобщённый закон взаимности и

13Scheidler R. Applications of Algebraic Nuniber Theory to Cryptography. PhD Dissertation, University of Manitoba (Canada), 1993. (http://math.ucalgary.ca/ rscheidl/Papers/my-thesis.pdf)

алгоритм евклидового нормирования Ленстры, был приведён для г = 7.14 Там же были, например, приведены явные формулы для , ,

. Методы, используемые в данных работах, можно обобщить для других r-степенных символов при небольших значениях г, однако это выходило за рамки нашего исследования.

Помимо r-степенных символов нас интересовал вопрос о вычислении символов степени гк. Именно этому посвящена пятая глава диссертации. В ней доказано, что для символов специального вида данный вопрос можно полиномиально свести к символам r-ой степени, а именно, получены формулы «подъёма» символа степенного вычета для некоторых частных случаев, используемых в теоремах 6 и 14.

Пусть т = гк для некоторого простого г, а - корень f(x) в его поле разложения, К = Ki = Q(o", Рассмотрим разложения идеала

(р) в кольцах целых алгебраических:

(р) = 7Г17Г2 • ... • 7ГП В ZK, (3)

(р)= (4)

Обозначим за 7?/ продолжение идеала 7Г- в Zr.

В пятой главе диссертации сформулированы и доказаны две следующие теоремы.

Теорема 15. Пусть 7г - идеал из разложения (S), тг' - идеал из разложения (4) и 7Г | 5г'. Пусть д(х) - образующий в поле GF(p)[x]/(f(x)), для которого известно, что (j^j k — Пустъ для некоторого а(х) требуется определить такое с € N, что t = 0 < с < гк. Обозначим ао(х) = а(х). Тогда с является решением системы:

(*>);-(*i)r. *oSe) <„

при i € {l,...,fc — 1} :

аЦх) ~ Oi-i(х)д~с<-1{х) (mod р, Да;));

где 0 < * < г, с = s(c0 + С\Т + С2Г2 + ... + Сцг*-1) (mod тк).

14Caranay P.C., Scheidler R. An efficient seventh power residue symbol algorithm. International Journal of Number Theory, 2009 (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.158.2501)

Следующая теорема во многом повторяет теорему 15, однако она позволяет существенно упростить вычисления. При возведении произвольного о(а;) £ (С^(р)[х]/(/(х)))* в степень ^fp мы получаем элемент порядкар-1, т.е. просто целое число по модулю р. Этот факт позволяет нам для случая

гк\\р — 1 перейти к вычислениям в простом подполе (т.е. просто по модулю Р)'

Теорема 16. Пусть т = тк - такое, что rk\\p - 1 (т.е. г f ^ff/ Пусть 7г - идеал из разложения (3), тг' - идеал из разложения (4) и т | тх'. Пусть g -образующий в поле GF(p), для которого (*) = Пусть для некоторого а(х) требуется найти такое с £ N, что = 0 < с < rk. Обозна-

чим ао = аСр^г(х) (mod р, /(х)). Тогда с является решением системы:

' (Яг =Ф)г' гдеО<Со<г;

при i £ {1,..., к — 1} : < аг{ = di-ig-*-1 (modp);

Ж = (|1> *Ь0<с<г;

с = s ■ (^Ег) • (со + Cir + с2г2 + ... + с*_у-1) (mod г*).

В теоремах 15 и 16 для нахождения а^ требуется извлечение корня г-ой степени. Это выполняется при помощи алгоритма Адлемана, Мандерса, Миллера12 являющегося обобщением алгоритма Шенкса. В данном

алгоритме требуется решать задачу дискретного логарифмирования в подгруппе порядка г, что равносильно вычислению символа r-степенного вычета15.

Недостатком данных теорем является необходимость вычисления символа степенного вычета степени гк для некоторого элемента поля. Однако, в некоторых случаях мы можем выбрать идеалы 7г и 7г' таким образом, что значение s, используемое в теоремах, будет известно.

В пятой главе диссертации рассмотрены три случая для rfc||p — 1, в которых мы можем получить число s, требуемое в теореме 16.

15Adleman L.M., Pomerance С., Rumely R.S. On Distinguishing Prime Numbers from Composite Number. Ann. Math. 117, 173-206, 1983.

Первый случай, d = 1, К = Q(£m)- В данном случае получаем, что 7Г = (р, £гк — 9**^) 11 к' — (Р> £г — 9^) (при этом выполнено, что 7г | тг'). Тогда = 1 и s = 1, т.е. последнее сравнение системы перепишется как

с = с0 + cir + с2г2 + ... + ск-1Гк~1 (mod гк).

Второй случай. Пусть d > 1, а € Q(fr*)> т-е- К = Q(£rt). Тогда получим, что разложение на множители идеала (р) имеет вид:

(Р)= П (5)

(Si,r')=l

Пусть 7Г{ = (р, £rk — тогда Л^тг,-) = р для всех г. Выберем 7г =

(Pi fr* — При этом получим, что 5 = 1, т.е. последнее сравнение си-

стемы перепишется как

с = ' ^ + °1Г + C2f2 + "' + Ck~irk~^ ^mod

Заметим, что если а € Q(fr)> то в Ki = Q(£r) имеет место разложение (р), аналогичное (5). Тогда в качестве 7г' можно выбрать (р, £г — д^)-

Третий случай. Пусть а & Q(fm) и а + £т - £'т((г, т) = 1) не являются корнями f{x). Тогда Q(a, fm) = Q(0), где 0 = <7 +

Найдём Q(x) - минимальный многочлен элемента в и рассмотрим его разложение на множители по модулю р. Обозначим за о\ = <т, <72, •••, Oi- все корни f(x).

Рассмотрим многочлен:

(sum)-1 j=1

Лемма 12. Пусть g - произвольный первообразный корень по модулю р. Тогда

Р(х) = Ц f(x-g^) (modp).

(si,m)=l

Поскольку в - корень Р(х), то для его минимального многочлена Q(x) и некоторого набора индексов I выполнено:

= (mod р).

is/

Предположим, что р2 { d(Q). Тогда ш

Обозначим 7Tj = (р, /(£m + а - д^3')). При этом М(щ) = pd. Таким образом, для данного случая мы также можем найти s, требуемое в теореме. А именно, s = s~l • ^fy- (mod m), то есть последнее сравнение системы перепишется как

с = si1 ■ (со + cir + с2г2 + ... + irA_1) (mod rA).

Таким образом, в рассмотренных случаях вычисление г^-степенного вычета полиномиально сводится к вычислению символов r-степенного вычета для некоторых элементов.

В заключении диссертации подводятся основные итоги работы, а также указаны возможные дальнейшие темы для исследования. Вопросы, рассмотренные в диссертации, могут получить дальнейшее развитие в следующих направлениях:

• вычисление символов г-степенного вычета для некоторых простых г;

• получение явного вида простых делителей идеала (р), для которых можно явно выписать значение ) в случае ггг{ р - 1;

\ / m

• исследование вопроса эквивалентности вычисления символов степенного вычета и проверки разрешимости задачи дискретного логарифмирования.

Автор выражает благодарность научному руководителю, кандидату физико-математических наук, доценту Михаилу Алексеевичу Черепнёву за постановку задач и помощь в работе.

Автор благодарит кандидата физико-математических наук, доцента Антона Александровича Клячко за ценные советы.

Автор благодарит коллектив кафедры теории чисел и отделения аспирантуры механико-математического факультета за поддержку.

Публикации автора по теме диссертации

1. Маркелова A.B. О разрешимости задачи дискретного логарифмирования. Вестник МГУ, сер.1. Матем. Механ., 2008, №6, с. 6-9.

2. Маркелова A.B. Дискретное логарифмирование в произвольных фак-торкольцах многочленов от одной переменной над конечным полем. Дискретная математика, 2010г., том 22, выпуск 2, стр. 120-132.

3. Маркелова A.B. О разрешимости задачи дискретного логарифмирования в кольце вычетов по составному модулю. Математика и безопасность информационных технологий. Материалы конференции в МГУ 28-29 октября 2004 г. С.185-191. М.: МЦМНО, 2005

Отпечатано в отделе оперативной печати Геологического ф-та МГУ Тираж 1£0 экз. Заказ № 5*

Обозначения

1 Введение

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

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

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

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

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

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

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

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

2.2 Полиномиальное сведение к случаю М - pq.

2.3 Разрешимость сравнения ах = b (mod pq).

2.4 Общий критерий разрешимости

3 Подъём решений показательного сравнения в факторкольце многочленов. Подъём решений показательного сравнения в цепных кольцах

3.1 Постановка задачи.

3.2 Подъём решений по степени неприводимого многочлена.

3.3 Подъём решений в цепных кольцах

3.4 Оптимизация алгоритма подъёма решений и проверки разрешимости

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

4.1 Полиномиальное сведение к случаю F(x) = fi(x)f2(x).

4.2 Использование обобщённого символа Якоби (квадратичного характера в кольце многочленов) для проверки разрешимости в частных случаях.

4.3 Связь задачи дискретного логарифмирования в поле с вычислением символов степенного вычета.

4.4 Разрешимость сравнения an(x) = b(x) (mod р, fi(x)f2(x))

4.5 Общий критерий разрешимости

5 О вычислении символов степенного вычета специального вида

5.1 Общие теоремы.

5.2 Способ выбора идеалов в частных случаях.

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

Задача дискретного логарифмирования является одной из ключевых задач современной теории чисел. В [1] (п.3.6) приводится следующая классификация видов этой задачи.

Задача дискретного логарифмирования (DLP): имея простое число р, первообразный корень а е (Z/pZ)* и некоторый элемент /9 G (Z/pZ)*, найти целое число х, 0 < х < р — 2, для которого ах = /3 (mod р).

Обобщённая задача дискретного логарифмирования (GDLP'): имея конечную мультипликативную циклическую группу G порядка п, порождающий элемент этой группы а и некоторый элемент этой группы /3, найти целое число х, 0 < х < п — 1, для которого ах = ¡3.

Обобщение GDLP: в произвольной конечной мультипликативной группе G для некоторых элементов а,/3 е G найти целое число х, для которого ах = ¡3, если такой х существует.

В последнем случае не требуется, чтобы группа G была циклической, а элемент а был образующим. Такая постановка задачи в общем случае может оказаться сложнее, чем GDLP. При этом если группа G является циклической и известен порядок п элемента а, то легко проверить, существует ли требуемое решение х: в этом случае решение сравнения ах = /3 существует тогда и только тогда, когда ¡Зп = 1 ([1], 3.54).

Хочется отметить, что многие авторы не следуют подобной классификации и обобщение СБЬР называют просто задачей дискретного логарифмирования ([2], [3], [4] и пр.). Поскольку в дальнейшем мы будем рассматривать именно обобщение СБЬР, то для простоты формулировок, мы тоже будем пользоваться термином "дискретное логарифмирование" именно в таком, наиболее общем, смысле.

В общем случае не известно полиномиального алгоритма решения задачи дискретного логарифмирования. На сложности этой задачи в простом поле базируется множество криптоалгоритмов, таких как алгоритм выработки общего ключа Диффи-Хеллмана ([5]), алгоритм выработки электронной цифровой подписи Эль-Гамаля ([6]), алгоритм выработки цифровой подписи ББА ([7]), предыдущий российский стандарт электронной цифровой подписи ГОСТ Р 34.10-94. На данный момент эти алгоритмы считаются устаревшими, им на смену пришли аналоги, вычисляемые в группе точек эллиптической кривой: ЕСБН, ЕСББА ([8]), ГОСТ Р 34.10-2001 ([9]).

Данный переход стал следствием успешного применения субэкспоненциальных алгоритмов для дискретного логарифмирования по модулю р ([Ю], [11] и т.д.) при том, что для эллиптической кривой общего вида не существует хоть сколько-то эффективных алгоритмов дискретного логарифмирования.

Тем не менее, несмотря на значительные достижения и новые разработки, для дискретного логарифмирования в конечных полях по-прежнему не существует полиномиального алгоритма, и данный вопрос продолжает волновать ведущих математиков всего мира.

В нашей работе мы будем рассматривать задачу дискретного логарифмирования в конечных кольцах, которые являются не менее важным криптографическим объектом, чем конечные поля. Вопрос дискретного логарифмирования в конечных кольцах зачастую полиномиально сводится к дискретному логарифмированию в конечных полях. Но в случае, если мультипликативная группа кольца не является циклической, возникает дополнительный вопрос: вопрос о существовании решения показательного сравнения.

Хочется подчеркнуть, что в данном случае вопрос не сводится к дискретному логарифмированию (или к проверке разрешимости) в поле. Нашей задаче будет научиться проверять разрешимость заданного сравнения, не решая его. Мы хотим получить критерии разрешимости, проверка которых была бы существенно проще решения задачи дискретного логарифмирования.

В [4] приведён алгоритм для проверки разрешимости в произвольной абе-левой группе. Данный алгоритм для конечной мультипликативной абелевой группы 6? и элементов а,/3 € С за 0(л/|(о;)|) умножений проверяет, принадлежит ли элемент /3 циклической группе (а), порождённой элементом а, и в случае положительного ответа находит /3. Для проверки используется таблица, состоящая из 0{л/\[а)\) пар элементов.

Данный алгоритм малоинтересен, поскольку имеет слишком большую сложность. Естественно ожидать, что при рассмотрении задачи не в произвольной группе, а в мультипликативной группе некоторого конкретного конечного кольца, структура которого нам хорошо известна, сложность окажется существенно меньше.

Этой темой ранее занимался О.Н.Василенко. Он рассматривал вопрос о разрешимости показательного сравнения в кольце вычетов по составному модулю ([12]) и в факторкольце многочленов над конечным полем ([13]). Им были получены некоторые критерии разрешимости для частных случаев. В нашей работе мы продолжим исследования О.Н.Василенко и обобщим критерии, полученные им, на случай произвольных параметров задачи.

Прежде всего, рассмотрим задачу дискретного логарифмирования в кольце вычетов по составному модулю. О.Н.Василенко сформулировал и доказал следующую теорему.

Теорема В1 ([12]; [2], т.5.28). Пусть М = р\ • . • Рк, где все рг

Уг различные нечётные простые ир{ — 1 = 2 [] р^3, гдерц - нечётные простые, 1 различные для всех г,у. Предположим, что ог6.Рга = р^ — 1 для г = 1,., t и огс1рга = для г — £ + 1,., к. Сравнение

Данная теорема позволяет проверять разрешимость показательного сравнения по нечётному составному модулю, не содержащему квадратов в ах == Ъ (mod М) разрешимо тогда и только тогда, когда разложении, при условии, что все простые делители модуля имею специальный вид, а порядок а по модулям делителей строго равен одному из двух значений.

Далее, интерес представляет вопрос о разрешимости показательного сравнения в факторкольце многочленов над полем. Cohen Н., Dyaz у Dyaz F., Olyver М. в 1998 году ([14]), затем Hess F., Pauli S., Pohst M.E. в 2003 году ([15]) и позднее Поповян И.А. в 2006 году ([16]) рассматривали задачу подъёма решений показательного сравнения в кольце целых алгебраических чисел. Было доказано, что решение сравнения ax = ß (mod 7TU) для некоторых а, ß 6 Zjk и простого идеала 7г полиномиально сводится к нахождению решения сравнения ах = ß (mod 7г).

Такое сведение осуществлялось при помощи различных логарифмических функций, а именно частных Ферма специального вида, р-адических логарифмов и логарифмов Артина-Хассе.

Частным случаем рассматриваемой задачи является сравнение вида an{x) = b{x) (mod р'у, f{x)), где многочлен f(x) со старшим коэффициентом 1 неприводим по модулю простого р.

При этом решение задачи сводится к нахождению решения сравнения ап(х) = Ъ{х) (mod р, f{x)).

Однако, решение последнего сравнения можно "поднимать" не только по степеням р, но и по степеням f(x). Этот вопрос рассматривался О.Н. Василенко, и им были получены следующие результаты.

Теорема В2 ([13]; [2], т.5.37). Пусть р/2 <v <р, orda(x) = ordb(:c) = р и а(х) ~ 1 + aP{x)f(x) + . + а^~1\х)Г-\х) (mod р, Г(х)),

Ь(х) = 1 + b^\x)f(x) + . + Ь^-1\х)Г-\х) (mod р, f(x)), где deg а®(х) < deg f{x), deg b®(x) < deg f(x). Если a^(x) ^0« сравнение an{x) = b(x) (mod p, f{x)) разрешимо относительно переменной n E N, mo n={bw(x)a^){x)-1)p (mod p, f(x)).

Теорема B3 ([13]; [2], т.5.39). Пусть p/2 < v < p, d = deg/{x), orda(a;) = p8\, ordb(x) = p^, \pd — l и a{xfd-1 = 1 + aP\x)f{x) + . + f^"1 (x) (mod p, fu(x)), bixf-1 = 1 + b^{x)f(x) + . + Ь^~1\х)Г~1(х) (mod p, fv(x)), где dega^(x) < d, degb^\x) < d. Пусть ail\x) 0.

1) Предположим, что найдётся € Ъ, для которого выполнено сравнение щ = (b^(х)а^(ж)1)р (mod р, f{x)). Если a{x)pd~l)no ~ b(x)pd-1 (mod р, fd(x)), то ап(х) = b{x) (mod р, fv{x)) разрешимо.

2) Если класс вычетов (ftW(ж)а(1)(ж)1)р (mod f(x)) не содержит элемента щ е Z или содержит, но (a{x)pd~l)n° ф b{x)pd~~l (mod р, fv{x)), то ап{х) = Ъ{х) (mod р, fv{x)) неразрешимо. •

Данные теоремы накладывают существенные ограничения на значение у и на порядки элементов а{х) и Ъ{х), что не позволяет их использовать в общем случае.

Заключение

В работе рассматривалась разрешимость задачи дискретного логарифмирования в некоторых видах конечных колец. В частности, были рассмотрены кольца вычетов по составному модулю и факторкольца многочленов одной переменной над конечным полем. Данный класс колец охватывает (с точностью до изоморфизма) все конечные коммутативные кольца главных идеалов с единицей.

Ранее данный вопрос был мало освещён в литературе. Преимущественно рассматривался вопрос решения показательного сравнения или вопрос полиномиального сведения дискретного логарифмирования в различных кольцах к дискретному логарифмированию в поле. Некоторые случаи были рассмотрены О.Н.Василенко, однако в них предполагались слишком серьёзные ограничения на параметры задачи.

Отдельно мы рассмотрели случай факторкольца по степени неприводимого многочлена. Была решена задача о подъёме решений и приведён конструктивный полиномиальный алгоритм для такого подъёма. Т.е. вопрос о дискретном логарифмировании в факторкольце многочленов был полиномиально сведён к дискретному логарифмированию в поле. Данный результат обобщает известные результаты О.Н.Василенко, верные для частных случаев.

В том числе были рассмотрены цепные кольца, заданные в канонической форме. Для них также получен критерий разрешимости и решена задача подъёма решений. Было показано, что в некоторых случаях конструктивный изоморфизм в цепные кольца помогает оптимизировать проверку разрешимости показательного сравнения.

Как оказалось, в общем случае вопрос о существовании решения показательного сравнения без его непосредственного решения является достаточно сложным и не всегда возможно построить полиномиальный алгоритм для такой проверки.

Достаточно легко выполняется редукция задачи. А именно, доказано, что в случае кольца вычетов нам необходимо и достаточно научиться проверять разрешимость сравнения по модулю произведения двух нечётных простых чисел, а в случае факторкольца многочленов - разрешимость сравнения по модулю произведения двух различных неприводимых над рассматриваемым полем многочленов.

Кроме того, нам удалось построить критерий, содержащий ряд формул, выполнение которых эквивалентно разрешимости задачи дискретного логарифмирования. В данных формулах используются символы степенного вычета для некоторых степеней. Такие критерии сформулированы и для редуцированных задач и для задач общего вида.

Нашей гипотезой является, что вопрос проверки разрешимости эквивалентен вычислению символов степенного вычета для заданных делителей. Т.е. мы предполагаем, что нет принципиально более простых алгоритмов проверки существования решения, чем вычисление упомянутых символов. Однако на данный момент вопрос обратного сведения (т.е. сведения вычисления символов к проверке разрешимости) остаётся открытым.

Вопрос о проверке разрешимости полиномиально свёлся к вопросу о вычислении символов степенного вычета. В связи с этим последняя глава данной работы была посвящена вопросам вычисления символов степенного вычета. Задача вычисления символов степенного вычета в общем случае является достаточно сложной. Однако в некоторых частных случаях её можно существенно упростить. А именно, для символов г^-степенного вычета, где гк\\р — 1, был приведён алгоритм полиномиального сведения к вычислению символов степенного вычета г-ой степени.

Существующие алгоритмы вычисления символов г-степенного вычета (например, для г — 2,3, 5, 7) в совокупности с доказанной теоремой о "подъёме" символов позволяют применять сформулированные критерии разрешимости для достаточно широкого класса задач. Но по-прежнему остаётся широкий набор параметров задачи, при которых сформулированные критерии проверки разрешимости не являются конструктивными.

Таким образом, вопросы, рассмотренные в данной работе, могут получить дальнейшее развитие в следующих направлениях:

• вычисление символов г-степенного вычета для некоторых простых г;

• получение явного вида простых делителей идеала (р), для которых можно явно выписать значение ( ) в случае т\р — 1; я / ш

• исследование вопроса эквивалентности вычисления символов степенного вычета и проверки разрешимости задачи дискретного логарифмирования.

1. Menezes A., Van Oorschot P.C., Vanstone S.A. Handbook of applied cryptography. CRC Press, 1997

2. Василенко О.H. Теоретико-числовые алгоритмы в криптографии. М.: МЦНМО, 2003.

3. Odlyzko A.M. Discrete logarithms in finite fields and their cryptographic significance. Advances in Cryptology-Proceedings of EUROCRYPT 84 (LNCS 209% 224-314, 1985.

4. Buchmann J., Jacobson M.J., Teske E. On some computational problems in finite abelian groups. Mathematics of Computation, 1997, V. 66 (220), p. 1663-1687.

5. Diffie W., Hellman M. E. New Directions in Cryptography. IEEE Transactions on Information Theory, Vol. IT-22, No. 6, November 1976, pp. 644-654.

6. ElGamal T. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, Vol. IT-31, No. 4, July 1985, pp. 469-472.

7. FIPS 186 Digital signature standard, Federal Information Processing Standards Publication 186, U.S. Department of Commerce/ N.I.S.T., National Technical Information Service, Springfield, Virginia, 1994.

8. Jonson D., Menezes A. The elliptic curve digital signature alghoritm. Technical report CORR 99-31, Dept. of C&O, University of Waterloo, Canada, 1999.

9. ГОСТ Р 34.10-2001. Государственный стандарт Российской Федерации. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи.

10. Gordon D.M. Discrete logarithms in GF(p) using the number field sieve. SI AM Journal on Discrete Mathematics, 6 (1993), 124-138.

11. Schirokauer O. Discrete logarithms and local units. Philosophical Transactions of the Royal Society of London A, 345 (1993), 409- 423.

12. Василенко O.H. О разрешимости задачи дискретного логарифмирования в кольцах вычетов. Фунд. и прикл. матем, 2002. 8, № 3. 647-653.

13. Василенко О.Н. О дискретном логарифмировании в некоторых группах. Вестник МГУ, сер.1. Матем. Механ., 2000, №5, с. 53-55.

14. Cohen Н., Diaz у Diaz F., Oliver М. Computing ray class groups, conductors and discriminants. Math. Сотр., Vol. 67:222, 1998, pp. 773-795.

15. Hess F., Pauli S. , Pohst M.E. Computing the multiplicative group of residue class rings. Math. Сотр., Vol. 72:243, 2003, pp. 1531-1548.

16. Поповян И.А. Подъём решений показательного сравнения. Математические заметки, 2006, 80:1, с.76-86

17. Riesel Н. Some soluble cases of the discrete logarithm problem. BIT, v28, no4, 1988.

18. Dickson L.E. History of the theory of numbers. V I. Divisibility and primality. New York, 1952.

19. Нестеренко Ю.В., Частные Ферма и р-адические логарифмы. Труды по дискретной математике, т. 5, М. "Физматлит", 2002, с. 173-188.

20. Сидельников В.М. Частные Ферма и логарифмирование в мультипликативной группе кольца вычетов по примарному модулю. Математические вопросы кибернетики, 1999. 8. 55-62.

21. Черепнёв М.А. О некотором свойстве дискретного логарифма. Тез.докл. XII межд. конф. "Проблемы теоретической кибернетики", Н. Новгород, 1999.

22. Artin Е., Tate J. Class Field Theory. 1968, W.A.Benjamin, Inc.

23. Ван дер Варден Б.JI. Алгебра. Наука, Москва, 1976.

24. Bach Е., Shallit J. Algorithmic number theory. V. 1. MIT Press, Massachusetts, 1996.

25. Scheidler R. Applications of Algebraic Number Theory to Cryptography. PhD Dissertation, University of Manitoba (Canada), 1993. (http://math.ucalgary.ca/ rscheidl/Papers/my-thesis.pdf)

26. Caranay P.C., Scheidler R. An efficient seventh power residue symbol algorithm. International Journal of Number Theory, 2009 (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.158.2501)

27. Adleman L.M., Pomerance C., Rumely R.S. On Distinguishing Prime Numbers from Composite Number. Ann. Math., 117, 173-206, 1983.

28. Виноградов И.М. Основы теории чисел. М.: Наука, 1972.

29. Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. М.:Мир, 1987

30. Pohst М. Computational algebraic number theory. Basel, Boston, Berlin: Birkhauser, 1993.

31. Алгебраическая теория чисел. Под редакцией Касселс Дж., Фрёлих А. М.: Мир, 1969

32. Cohen Н. A course in computational algebraic number theory. SpringerVerlag, Berlin, 1993.

33. Елизаров В.П. Конечные кольца. Гелиос АРВ, Москва, 2006.

34. Галочкин А.И., Нестеренко Ю.В., Шидловский А.Б. Введение в теорию чисел. М.: Изд-во Моск. Ун-та, 1984

35. Публикации автора по теме диссертации

36. Маркелова A.B. 0 разрешимости задачи дискретного логарифмирования. Вестник МГУ, сер.1. Матем. Механ., 2008, №6, с. 6-9.

37. Маркелова A.B. Дискретное логарифмирование в произвольных фактор-кольцах многочленов от одной переменной над конечным полем. Дискретная математика, 2010г., том 22, выпуск 2, стр. 120-132.

38. Маркелова A.B. О разрешимости задачи дискретного логарифмирования в кольце вычетов по составному модулю. Математика и безопасность информационных технологий. Материалы конференции в МГУ 28-29 октября 2004 г. С.185-191. М.: МЦМНО, 2005