Московский Государственный Университет
имени М.В. Ломоносова
Механико-математический факультет
На правах рукописи
УДК 511.2
Маркелова Александра Викторовна
РАЗРЕШИМОСТЬ ЗАДАЧИ ДИСКРЕТНОГО
ЛОГАРИФМИРОВАНИЯ В КОЛЬЦАХ
Специальность 01.01.06 - математическая логика, алгебра и теория чиселАВТОРЕФЕРАТ
диссертации на соискание учёной степени кандидата физико-математических наук
Москва, 2011
Работа выполнена на кафедре теории чисел Механико-математического факультета Московского государственного университета имени М.В. Ломоносова.
Научный руководитель: кандидат физико-математических наук, доцент Михаил Алексеевич Черепнёв
Официальные оппоненты: доктор физико-математических наук, профессор Владимир Григорьевич Чирский кандидат физико-математических наук Вадим Владиславович Назаров
Ведущая организация: Институт информационных наук и технологий безопасности (ИИНТБ) РГГУ
Защита диссертации состоится 11 марта 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 и элементов, G за O( | |) умножений проверяет, принадлежит ли элемент циклической группе, порождённой элементом, и в случае положительного ответа находит log. Для проверки используется таблица, состоящая из O( | |) пар элементов.
Данный алгоритм малоинтересен, поскольку имеет слишком большую сложность. Естественно ожидать, что при рассмотрении задачи не в произвольной группе, а в мультипликативной группе некоторого конкретного конечного кольца, структура которого нам хорошо известна, сложность окажется существенно меньше.
Этой темой занимался О.Н.Василенко. Он рассматривал вопрос о разрешимости показательного сравнения в кольце вычетов по составному модулю и в факторкольце многочленов над конечным полем3. Им были получены некоторые критерии разрешимости для частных случаев.
Прежде всего, рассмотрим задачу дискретного логарифмирования в кольце вычетов по составному модулю. О.Н.Василенко сформулировал и доказал Buchmann J., Jacobson M.J., Teske E. On some computational problems in nite abelian groups.
Mathematics of Computation, 1997, V. 66 (220), p. 1663-1687.
Василенко О.Н. О разрешимости задачи дискретного логарифмирования в кольцах вычетов. Фунд. и прикл. матем, 2002. 8, № 3. 647-653.
Василенко О.Н. О дискретном логарифмировании в некоторых группах. Вестник МГУ, сер.1. Матем.
Механ., 2000, №5, с. 53-55.
теорему2, позволяющую проверять разрешимость показательного сравнения для M = p1 ·... · pk, где все pi - различные нечётные простые, имеющие специальный вид, при условии, что порядок a по модулям pi строго равен одному из двух значений pi 1 или pi2.
Далее, интерес представляет вопрос о разрешимости показательного сравнения в факторкольце многочленов над полем. Cohen H., Dyaz y Dyaz F., Olyver M. в 1998 году4, затем Hess F., Pauli S., Pohst M.E. в 2003 году5 и позднее Поповян И.А. в 2006 году6 рассматривали задачу подъёма решений показательного сравнения в кольце целых алгебраических чисел. Было доказано, что решение сравнения для некоторых, ZK и простого идеала полиномиально сводится к нахождению решения сравнения Такое сведение осуществлялось при помощи различных логарифмических функций, а именно частных Ферма специального вида, p-адических логарифмов и логарифмов Артина-Хассе.
Частным случаем рассматриваемой задачи является сравнение вида где многочлен f (x) со старшим коэффициентом 1 неприводим по модулю простого p.
При этом решение задачи сводится к нахождению решения сравнения Cohen H., Diaz y Diaz F., Oliver M. Computing ray class groups, conductors and discriminants. Math.
Comp., Vol. 67:222, 1998, pp. 773-795.
Hess F., Pauli S., Pohst M.E. Computing the multiplicative group of residue class rings. Math. Comp., Vol.
72:243, 2003, pp. 1531-1548.
Поповян И.А. Подъём решений показательного сравнения. Математические заметки, 2006, 80:1, с.76- Однако, решение последнего сравнения можно ”поднимать” не только по степеням p, но и по степеням f (x). Вопрос о подъёме решений сравнения рассматривался О.Н.Василенко3, и им были получены некоторые результаты для случая p/2 < p, orda(x) = p1, ordb(x) = p2, 2 |1 |pd (d = degf (x)) при условии, что a f (x) данных ограничениях и в случае разрешимости сравнения (1) были получены формулы для подъёма решений этого сравнения.
Цель работы Цель диссертации - получение конструктивных критериев разрешимости задачи дискретного логарифмирования в кольцах вычетов по произвольному составному модулю и в факторкольцах многочленов над конечными полями, подъём решений показательного сравнения в факторкольцах многочленов над конечными полями по степени неприводимого многочлена, оптимизация вычислительной сложности полученных алгоритмов.
Научная новизна Результаты диссертации являются новыми и состоят в следующем:
• Получен критерий разрешимости показательного сравнения в кольце вычетов по модулю составного числа. Доказано, что вопрос о разрешимости показательного сравнения по модулю произвольного составного числа полиномиально сводится к вычислению символов степенного вычета с некоторыми простыми индексами, являющимися делителями p1, где p|M. Приведён конструктивный полиномиальный алгоритм такого сведения. Итоговая теорема обобщает полученные О.Н.Василенко критерии.
• Решена задача подъёма решений по модулю степени неприводимого многочлена над конечным полем. Приведён алгоритм её полиномиального сведения к аналогичной задаче по модулю самого неприводимого многочлена.
Итоговая теорема обобщает критерии О.Н.Василенко.
• Решена задача подъёма решений показательного сравнения в цепных кольцах. Описаны возможные оптимизации алгоритма подъёма решений по модулю степени неприводимого многочлена над конечным полем при помощи построения конструктивных изоморфизмов в цепные кольца. Получены оценки сложности предлагаемых модификаций.
• Получен критерий разрешимости показательного сравнения по модулю произвольного многочлена над конечным полем. Доказано, что вопрос о разрешимости полиномиально сводится к вычислению символов степенного вычета.
• Получены формулы для “подъёма” символа степенного вычета в ряде случаев, используемых в доказанных выше критериях разрешимости. А именно, показано, что в случае, когда rk ||p 1, вычисление символа степени rk полиномиально сводится к вычислению символов степени r, где r - простое.
Основные методы исследования В диссертации используются методы алгебраической теории чисел, теории конечных колец, теории сложности вычислений.
Теоретическая и практическая ценность В диссертации доказываются теоремы и выводятся формулы, которые могут найти применение в алгебраической теории чисел. Построенные алгоритмы с оценками сложности могут использоваться в вычислительной теории чисел.
Апробация работы Результаты диссертации докладывались автором на следующих научных семинарах и конференциях:
• на научно-исследовательском семинаре по теории чисел под руководством проф. Ю.В.Нестеренко, проф. Н.Г.Мощевитина (2008 г., 2010 г.);
• на семинаре “Теоретико-числовые вопросы криптографии” под руководством доц. М.А.Черепнёва (2008 г., 2009 г., 2010 г.);
• на конференции “Ломоносовские чтения” (Москва, 2009 г.);
• на конференции “Математика и безопасность информационных технологий” (Москва, 2004 г., 2009 г., 2010 г.).
Публикации Результаты автора по теме диссертации опубликованы в 3 работах, список которых приводится в конце автореферата [1-3].
Структура и объём диссертации Диссертация состоит из введения, четырёх глав, заключения и библиографии (37 наименований). Общий объём диссертации составляет 89 страниц.
Содержание работы Во введении, являющемся первой главой, описывается структура диссертации, обосновывается актуальность темы и научная новизна полученных результатов, излагаются основные результаты диссертации.
Во второй главе сформулирован и доказан критерий разрешимости сравнения где M = p1 ·... · pk, pi - различные простые, i N, a, b (Z/M Z).
Для случая k = 1 разрешимость проверяется с использованием частных Ферма Q(a, r) = a r 1 (mod r) по следующим теоремам.
Теорема 1. Для M = p, где p - простое, нечётное, > 1, сравнение (2) равносильно системе Теорема 2. Для M = 2, 5 сравнение (2) равносильно системе Данные теоремы широко7,8,9 известны для случая, когда a - первообразный по модулю простого нечётного p или a = 5 при p = 2. Однако, они верны и для произвольного a. Эти теоремы полезны не только для проверки разрешимости, но и для подъёма решений показательного сравнения. Решения линейных сравнений приведённых выше систем будут использоваться в следующей теореме.
пар (i, j). Обозначим через ci решение сравнения ax b (mod pi ) по модулю i, а через ci - его вычет по модулю pi. Сравнение (2) разрешимо тогда и только тогда, когда выполнены следующие условия:
В результате исходная задача редуцируется к случаю, когда k = 2, p1, p - нечётные, 1 = 2 = 1.
Далее в главе 2 сформулирован следующий критерий разрешимости показательного сравнения по модулю pq для некоторых частных случаев.
Лемма 3. Пусть p = 2r + 1, q = 2s + 1, где (r, s) = 1, r и s - нечётные.
Сравнение разрешимо тогда и только тогда, когда:
1) ax b разрешимо по модулям p и q;
Совокупность данной леммы и теоремы 3 даёт обобщение результатов О.Н.Василенко2. В частности, можно отказаться от условия i = 1, снять ограничения на чётность M и на значения ordpi a.
В лемме 3 для проверки разрешимости используется символ Лежандра.
Для обобщения результатов на случай произвольных p и q нам потребуется Riesel H. Some soluble cases of the discrete logarithm problem. BIT, v28, no4, 1988.
Нестеренко Ю.В., Частные Ферма и p-адические логарифмы. Труды по дискретной математике, т.
5, М. “Физматлит”, 2002, с. 173-188.
Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. М.: МЦНМО, 2003.
обобщение символа Лежандра - символ степенного вычета.
Здесь приводится определение в соответствии с Artin E., Tate J.10.
Пусть задано поле K, являющееся конечным расширением Q, простой идеал в его кольце целых ZK, целое число m, и пусть K содержит m-ый корень из единицы m. При этом m | N 1. Для целого алгебраического определим символ степенного вычета следующим образом:
Данный символ является обобщением символа Лежандра и обладает аналогичными свойствами: периодичностью и мультипликативностью.
все ri - различные простые и (p, ri ) = (q, ri ) = (p, q ) = 1. Пусть заданы разложения на простые идеалы в кольцах целых алгебраических:
Обозначим j = j1 и j = j1.
1 |p, 2 |q. При этом для некоторых первообразных g1, g2. Причём (rj, s1j ) = (rj, s2j ) = 1.
Тогда для любого j при 1j = 0 и 2j = 0 однозначно определяются такие e1j и e2j, что 0 < e1j < rj 1j, 0 < e2j < rj 2j, что (e1j, rj ) = (e2j, rj ) = 1 и Artin E., Tate J. Class Field Theory. 1968, W.A.Benjamin, Inc.
При 1j = 0 (2j = 0) считаем e1j = 1 (e2j = 1).
Для вычисления чисел e1j, e2j необходимо и достаточно вычислить символы степенного вычета для a.
В этих обозначениях можно сформулировать следующую теорему, дающую критерий разрешимости показательного сравнения по модулю pq.
Теорема 6. Сравнение разрешимо в том и только том случае, когда ax b разрешимо по модулям p и q, и для всех j выполнено:
Совокупность теорем 3 и 6 даёт общий критерий разрешимости показательного сравнения в кольце вычетов.
В третьей главе диссертации рассматривается показательное сравнение в кольце R = GF (q)[x]/(f (x)), где q = pl, p - простое число, l N, N \{1}, а многочлен f (x) неприводим над GF (q)[x], имеет старший коэффициент 1 и degf (x) = d.
R является кольцом с однозначным разложением на простые множители11, и каждый элемент кольца R можно однозначно представить в виде:
a(x) a(0) (x) + a(1) (x)f (x) +... + a(1) (x)f 1 (x) (mod f (x)), Обозначим Ks (a(x)) = a(s) (x) - s-ый коэффициент в этом разложении.
Положим по определению K (a(x)) = 0.
Ван дер Варден Б. Л. Алгебра. Наука, Москва, 1976.
Если ordR u(x) = pµ, то u(x) 1 (mod f (x)). Таким образом, корректно определить следующую функцию:
Функция KD (aqd 1 (x)) (aq 1 (x)) фактически является аналогом частного Ферма в рассматриваемом факторкольце многочленов. С её помощью сформулирована и доказана теорема о подъёме решений в факторкольце по степени неприводимого многочлена над произвольным конечным полем.
Теорема 9 (о подъёме решений). Сравнение над полем GF (q) равносильно системе:
Ks(i) (bq 1 (x)a(q 1)(n0 +n1 p+...+ni1 p ) (x)) (mod f (x));
где ordR a(x) = pµ, |q d 1.
Используя теорему 9, нетрудно построить конструктивный полиномиальный алгоритм подъёма решений и проверки разрешимости в кольце R, сложность которого при l = 1 составляет O(d log(d)(d + log ) log p) арифметических операций в поле GF (p), а при l > 1 равна O(ld log l log(d)(dl + log ) log p) арифметических операций в поле GF (p). Кроме того, поскольку кольцо R является цепным, то можно построить конструктивный изоморфизм из R в R GF (pr )[x]/(xt ) (при r = ld, t = ), что позволяет в некоторых случаях оптимизировать алгоритм проверки разрешимости и подъёма решений.
В четвёртой главе сформулирован и доказан критерий разрешимости задачи дискретного логарифмирования в факторкольце по произвольному составному многочлену над полем GF (q), q = pl.
Как и в случае кольца вычетов, вначале получена теорема, сводящая проверку разрешимости по модулю произвольного приводимого многочлена к аналогичной задаче по модулю произведения двух различных неприводимых многочленов.
Теорема 11. Пусть F (x) = f1 1 (x) ·... · fk k (x), где все fi - различные неприводимые над полем GF (q), со старшими коэффициентами 1, k > 1, ordfii (x) a(x) = i = pµi i, где (p, i ) = 1. Обозначим через ni решение сравнения an (x) b(x) (mod fii (x)), а через ni его вычет по модулю pµi. Сравнение разрешимо тогда и только тогда, когда выполнены следующие условия:
1) i сравнение an (x) b(x) (mod fii (x)) разрешимо;
2) i = j сравнение an (x) b(x) (mod fi (x)fj (x)) разрешимо;
Отдельно в главе 4 рассмотрен частный случай задачи, использующий обобщение символа Якоби для многочленов, поскольку этот случай является наиболее простым с вычислительной точки зрения.
Если f (x) - неприводимый многочлен со старшим коэффициентом 1, то обобщённый символ Якоби определяется следующим образом12 :
Если f (x) = f1 (x) ·... · fr (x), где fi (x) - неприводимые, со старшими коэффициентами 1, то обобщённый символ Якоби определяется по мультипликативности: r Обобщённый символ Якоби обладает стандартными свойствами: мультипликативностью и периодичностью. Полиномиальный алгоритм вычисления Massachusetts, 1996.
обобщённого символа Якоби12 для произвольных многочленов f (x) и g(x) использует закон взаимности, а также квадратичный характер в поле GF (q) ((c) = c 2 ).
Лемма 9. Пусть p - нечётное простое, degf1 (x) = d1, degf2 (x) = d2, pld1 = 2r + 1, pld2 = 2s + 1, где (r, s) = 1, r и s - нечётные. Сравнение разрешимо тогда и только тогда, когда 1) an (x) b(x) разрешимо по модулям f1 (x) и f2 (x);
Например, данная лемма применима для произвольного a(x) в случае, если p = 3, l = 1, (d1, d2 ) = 1, di - нечётные.
Далее будем рассматривать задачу только над простым полем и обобщим лемму 9 на произвольный случай.
Пусть degf1 (x) = d1, degf2 (x) = d2, pd1 1 = r1 1...rs s p1, pd2 1 = r1 1...rs s p2, где ri - различные простые и (p1, ri ) = (p2, ri ) = (p1, p2 ) = 1.
Для всех j (1 j s) и i = 1, 2 введём следующие обозначения: i корень fi (x), Q(1, rj ) = K1j, Q(2, rj ) = K2j, ZKij - кольцо целых в Kij, (p) = j1 j2... - разложение на простые в ZK1j, j = j1, (p) = j1 j2... разложение на простые в ZK2j, j = j1.
Пусть далее ordf1 (x) a(x) = rj 1j 1j, ordf2 (x) a(x) = rj 2j 2j, где 0 1j j, 0 2j j, (rj, 1j ) = (rj, 2j ) = 1. При этом для некоторых порождающих элементов g1 (x) (mod f1 (x)) и g2 (x) (mod f2 (x)) выполнено где (rj, s1j ) = (rj, s2j ) = 1 для всех j (1 j s).
Тогда для любого j при 1j = 0 и 2j = 0 однозначно определяются такие При 1j = 0 (2j = 0) считаем e1j = 1 (e2j = 1).
Для нахождения чисел eij необходимо и достаточно вычислить символы степенного вычета для a(i ).
Теорема 14. Сравнение разрешимо тогда и только тогда, когда разрешимы аналогичные сравнения по модулям f1 (x) и f2 (x) и для всех j (1 j s) выполнено:
Таким образом, совокупность теорем 11 и 14 даёт критерий разрешимости показательного сравнения в произвольном факторкольце многочленов над конечным полем.
Вопрос о разрешимости показательного сравнения, как в случае кольца вычетов по составному модулю, так и в случае факторкольца многочленов, свёлся к вычислению символов степенного вычета. Полученные критерии являются конструктивными, только если вычисление соответствующих символов можно выполнить за полиномиальное время. Изучению этого вопроса посвящена пятая глава диссертации.
На данный момент вопрос о быстром вычислении r-степенного символа (для простого r) в общем случае остаётся открытым. Хорошо известен способ вычисления символа Лежандра (т.е. при r = 2). Scheidler R.13 (глава 7) описывает алгоритмы вычисления символов степенного вычета для r = 3, 5. В году аналогичный алгоритм, использующий обобщённый закон взаимности и 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) алгоритм евклидового нормирования Ленстры, был приведён для r = 7.,. Методы, используемые в данных работах, можно обобщить для других r-степенных символов при небольших значениях r, однако это выходило за рамки нашего исследования.
Помимо r-степенных символов нас интересовал вопрос о вычислении символов степени rk. Именно этому посвящена пятая глава диссертации. В ней доказано, что для символов специального вида данный вопрос можно полиномиально свести к символам r-ой степени, а именно, получены формулы подъёма символа степенного вычета для некоторых частных случаев, используемых в теоремах 6 и 14.
Пусть m = rk для некоторого простого r, - корень f (x) в его поле разложения, K = Q(, m ), K1 = Q(, r ). Рассмотрим разложения идеала (p) в кольцах целых алгебраических:
Обозначим за i продолжение идеала i в ZK.
В пятой главе диссертации сформулированы и доказаны две следующие теоремы.
Теорема 15. Пусть - идеал из разложения (3), - идеал из разложения (4) и |. Пусть g(x) - образующий в поле GF (p)[x]/(f (x)), для которого известно, что g() k = rk. Пусть для некоторого a(x) требуs ется определить такое c N, что a() k = rk, 0 c < rk. Обозначим a0 (x) = a(x). Тогда c является решением системы:
Caranay P.C., Scheidler R. An ecient 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, однако она позволяет существенно упростить вычисления. При возведении произвольного a(x) (GF (p)[x]/(f (x))) в степень pp1 мы получаем элемент порядка p 1, т.е. просто целое число по модулю p. Этот факт позволяет нам для случая rk ||p 1 перейти к вычислениям в простом подполе (т.е. просто по модулю p).
Теорема 16. Пусть m = rk - такое, что rk ||p 1 (т.е. r pp1 ). Пусть - идеал из разложения (3), - идеал из разложения (4) и |. Пусть g g s образующий в поле GF (p), для которого rk = rk. Пусть для некоторого чим a0 a (x) (mod p, f (x)). Тогда c является решением системы:
В теоремах 15 и 16 для нахождения ai требуется извлечение корня rой степени. Это выполняется при помощи алгоритма Адлемана, Мандерса, Миллера12 (гл. 7.3), являющегося обобщением алгоритма Шенкса. В данном алгоритме требуется решать задачу дискретного логарифмирования в подгруппе порядка r, что равносильно вычислению символа r-степенного вычета15.
«