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

На правах рукописи

УДК 511.225+511.23 Поповян Илья Ардашесович ПОДЪЁМ РЕШЕНИЙ ПОКАЗАТЕЛЬНЫХ УРАВНЕНИЙ В КОНЕЧНЫХ КОЛЬЦАХ 01.01.06 математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Москва, 2007

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

Научный консультант: кандидат физико-математических наук, доцент М.А. Черепнев

Официальные оппоненты: доктор физико-математических на ук, профессор В.Г. Чирский, кандидат физико-математических наук, Е.В. Горбатов

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

Защита диссертации состоится 18 мая 2007 г. в 16 ч. 15 мин. на заседании диссертационного совета Д.501.001.84 в Московском государственном университете им. М.В. Ломоносова по адресу: 119992, ГСП-2, Москва, Ленинские горы, МГУ, Механико-математический факультет, ауд. 14-08.

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

Автореферат разослан 18 апреля 2007 г.

Ученый секретарь диссертационного совета Д.501.001.84 в МГУ профессор В.Н. Чубариков

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

В современной криптографии важную роль играет понятие односто ронней функции. Односторонней называется такая вычислимая за по линомиальное время, то есть за время, равное многочлену от длины входа, функция, задача обращения которой неполиномиальна. Соглас но У. Диффи1 в середине 70-х годов Дж. Гилл предложил использовать в качестве одностороннего отображения возведение в степень по моду лю простого числа. Позже оно было обобщено до возведения в степень в произвольной конечной циклической группе, то есть если (G, ) – цик лическая группа, G = g, то Z G : n gn.

Задача обращения этого отображения называется (обобщенной) задачей дискретного логарифмирования (GDLP), а при G = (Z/(p)), где p – простое рациональное число, эта задача называется просто задачей дис кретного логарифмирования (DLP). На ее предположительной неполи номиальности основана стойкость многих асимметричных криптосхем, таких как, например, схема распределения ключей Диффи-Хэллмэна или схема электронной подписи Эль-Гамаля2 и ее варианты, DSA3 и ГОСТ-34.10-94.

Естественным обобщением DLP является GDLP для G = (Z/(m)), где m Z – составное. Задача полиномиального сведения GDLP в (Z/mZ) к DLP в группах (Z/pi Z), соответствующих всем простым делителям pi числа m, решена. Решение состоит в применении китай ской теоремы об остатках для сведения задачи в (Z/mZ) к задаче в (Z/pk Z), pk ||m, и так называемого подъёма решения.

Подъёмом решения в кольце целых рациональных чисел называется задача сведения GDLP в (Z/pk Z) к DLP в (Z/pZ). Одним из первых эту задачу в более общей постановке рассмотрел Г. Ризель4 и предложил использовать для ее решения аппарат частных Ферма. Свойства частных W. Die and M. E. Hellman, New Directions in Cryptography. IEEE Transactions on Information Theory, Vol. IT-22, No. 6, November 1976, pp. 644-654.

T. ElGamal, 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.

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

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

Ферма позволили ему свести задачу подъёма решения к линейным срав нениям, и использовать решения последних для нахождения дискретных логарифмов в (Z/(m)) при некоторых значениях m, в частности, при m = pk.

В 2002 году вышла статья Ю.В. Нестеренко5, в которой он показал возможность использования p -адических логарифмов вместо частных Ферма для подъёма решения в кольце Z, а также установил связь между этими функциями.

Частные Ферма обладают следующим свойством: их значения на пер вообразных корнях по модулю p не делятся на p. Это свойство обеспе чивает несократимость линейных сравнений, возникающих в процессе подъёма решения, что, в свою очередь, позволяет эффективно их ре шать. В работе М.А. Черепнева6 предложен способ модификации част ного Ферма таким образом, чтобы указанное свойство выполнялось и для произвольного элемента g (Z/pZ).

Естественным теоретико-числовым обобщением задачи подъёма ре шения показательного сравнения в Z является аналогичная задача с заменой кольца целых Z на кольцо целых ZK какого-либо конечного расширения K поля Q.

В 1979 году Н. Накагоши7 получил полное, хотя и не всегда кон структивное, описание мультипликативной группы ZK /pN, однако результат был малопригоден для практического применения. Почти лет спустя, в 1998 году, Г. Коэн, Ф. Диаз-и-Диаз и М. Оливер8, работая над алгоритмами вычислений в теории полей классов, впервые дали кон структивное описание мультипликативного базиса группы (ZK /m) по произвольному идеалу m кольца ZK. Рассматривая задачу нахождения представления произвольного элемента в заданном мультипликативном базисе группы (ZK /m), они свели ее к аналогичной задаче в ZK /pN, где p – простой идеал, такой что pN ||m. Далее они заметили, что для решения последней, являющейся родственной задаче подъёма решения, вполне естественно попытаться воспользоваться p -адическим логариф мом, и указали, что такой подход действительно срабатывает почти для Нестеренко Ю. В., Частные Ферма и p -адические логарифмы. “Труды по дискретной матема тике”, т. 5, М. “Физматлит”, 2002, с. 173-188.

Черепнев М. А., О некотором свойстве дискретного логарифма. Тез. докл. XII межд. конф.

“Проблемы теоретической кибернетики”. Н. Новгород, 1999.

Nakagoshi N., The structure of the multiplicative group of residue classes modulo pN +1. Nagoya Math. J., Vol. 73 (1979), 41-60.

Cohen H., Diaz y Diaz F., Oliver M., Computing ray class groups, conductors and discriminants.

Math. Comp., Vol. 67:222, 1998, pp. 773-795.

e всех идеалов. Однако при большом значении параметра p1, где e – ин декс ветвления идеала p, а p – простое рациональное, такое что p|(p), применить p -адический логарифм не удается. Поэтому вместо исполь зования p -адического логарифма они предложили индуктивный метод, названный квадратичным, позволяющий за [log2 N ] итераций получить представление произвольного элемента в заданном мультипликативном базисе уже для произвольного простого идеала p.

Продолжая тематику, в 1999 году в своей книге9 Г. Коэн предложил обобщить квадратичный метод при помощи так называемого логарифма Артина-Хассе. Также он заметил, что для решения задачи нахождения представления произвольного элемента в заданном мультипликативном базисе группы ZK /pN можно использовать комбинированный метод, совмещающий квадратичный метод и подход с p -адическим логариф мом, однако подробных решений не привел. В 2003 году вышла статья Ф. Гесса, Ч. Паули и М. Поста10, в которой указанный комбинированный метод был реализован, при этом были также получены оценки его слож ности в терминах операций с матрицами и арифметических операций с алгебраическими числами в соответствующих факторах.

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

Научная новизна работы.

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

1. Доказаны теоремы о подъёме решений показательных сравнений в кольцах целых алгебраических чисел, дающие новые явные формулы для вычисления решений с использованием логарифма Артина-Хассе и p -адического логарифма. Получены формулы для эффективного вычис ления логарифма Артина-Хассе и p -адического логарифма. На основе этих результатов построен полиномиальный алгоритм подъёма решений показательных сравнений в кольцах целых алгебраических чисел.

2. Подсчитана функция Кармайкла для некоторых специальных групп, связанных с группой главных единиц кольца целых p -адического пополнения произвольного поля алгебраических чисел.

3. Построены аналоги частных Ферма на подгруппах группы главных Cohen H., Advanced Topics in Computational Number Theory. GTM 193, Springer-NY, 1999.

Hess F., Pauli S., Pohst M. E., Computing the multiplicative group of residue class rings. Math.

Comp., Vol. 72:243, 2003, pp. 1531-1548.

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

Цель работы.

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

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

Методы исследования.

Работа опирается на исследования в теории алгебраических чисел и p -адическом анализе, а также на теоретико-числовые алгоритмы.

Для исследования свойств p -адического логарифма, логарифма Артина Хассе и оптимальных логарифмических функций, а также для вычис ления порядков элементов применяются методы теории алгебраических чисел и p -адического анализа. Для оценки сложностей предложенных алгоритмов – результаты теории сложности вычислений.

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

Работа носит теоретический характер. Результаты диссертации могут найти применение в теории алгебраических чисел, p -адическом анализе и вычислительной теории чисел.

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

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

1. Научно-исследовательский семинар по теории чисел под руковод ством Ю.В. Нестеренко и Н.Г. Мощевитина, механико-математический факультет МГУ (2003 г.);

2. Семинар „Теоретико-числовые вопросы криптографии“ под руко водством М.А. Черепнева и Ю.В. Нестеренко, механико-математический факультет МГУ (2004-2006 гг.).

3. Конференция „Математика и безопасность информационных тех нологий“, МГУ (2003 г.) 4. Конференция „Ломоносовские чтения“, МГУ (2006 г.) 5. Международная конференция „Диофантовы и аналитические про блемы теории чисел“, МГУ (2007 г.).

Публикации.

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

Структура и объем работы.

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

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ Пусть K – конечное расширение Q, ZK – его кольцо целых. Пусть также p – простой идеал ZK. Рассмотрим показательное сравнение x mod pN, x Z, (1) где N N\{1},, ZK \p. Задача сведения нахождения решения сравнения (1) к нахождению решения сравнения x mod p, x Z называется задачей подъёма решения показательного сравнения (1) в кольце ZK. Решению этой задачи посвящена вторая глава диссерта ции. В ней предложен алгоритм комбинированного типа с использовани ем логарифма Артина-Хассе и p -адического логарифма.

Пусть идеал p лежит над p Z и имеет индекс ветвления e и степень расширения f, то есть e N : pe ||(p) и f N : # (ZK /p) = pf.

e Обозначим = p1 +1 и пусть обозначает p -адический показатель в ZK. Зафиксируем также какой-либо элемент ZK, такой что () = 1.

Основной результат о подъёме решения разбивается на три случая и формулируется соответственно в одном утверждении и двух теоремах.

Первый, „вырожденный“, случай состоит в том, что f (p 1) N.

Утверждение 2.1. Пусть, ZK \p, N N\{1} и a = f (p 1 1) N (допустимо a = ).

Тогда f p 1 1 mod pN, x N mod p, x Z x mod p, x Z.

В следующей теореме рассматривается “низкий” случай, то есть f (p 1) N, возникающий из-за того, что в ZK индекс ветвления e идеала p может быть больше p. Для решения задачи подъёма в этом случае использу ется специальная функция, логарифм Артина-Хассе, задаваемая много членом p1 i i1 x L(1 + x) = (1).

i i= Обладающий свойствами, аналогичными свойствам обычных логариф мов, логарифм Артина-Хассе позволяет в несколько этапов провести подъём решения сравнения (1).

Лемма 2.1. Пусть x, y, z ZK, x p, 1 (y) (z), тогда I) (L(1 + x)) = (x).

II) L((1 + y)(1 + z)) L(1 + y) + L(1 + z) mod pp(y).

Далее для y R скобки y обозначают верхнюю положительную целую часть, то есть при y R, y 0 обозначим y N – минималь ное, такое что y y, а при y 0 положим y := 0.

f Теорема 2.1. Пусть, ZK \p, N {2,..., }, a = (p 1) N и t = logp N.

a Тогда x mod pN, x Z x t1 yi pi mod pt, yi {0, 1,..., p 1}, (T1.1) i= (pf 1) i j=0 yj pj yi L pi (pf 1) L i+ mod pap, (T1.2) i = 0,..., t 2 при t 2, (pf 1) t j=0 yj pj yt1 L pt1 (pf 1) L mod pN, (T1.3) x mod p, x Z. (T1.4) В следующей теореме рассматривается “высокий” случай, то есть f (p 1) N, N.

Процедура подъёма в этом случае состоит в использовании теоремы 2.1 при N = для нахождения части решения и дополнительном од нократном применении p -адического логарифма, определяемого на p адическом пополнении K рядом xn (1)n Logp (1 + x) =.

n n= Для 0 = 1 p обозначим logp N ( 1)p r() (1) R() :=, e где e e logp +1 logp (p1)(1) (p1)(1) p p 1) ( 1) e.

r() := ( Эти функции определяют мультипликативный порядок числа в фак торе ZK /pN.

f Теорема 2.2. Пусть, ZK \p, N N, N, a = (p f 1) N, t = logp a и R = R(p 1 ).

Тогда x mod pN, x Z x y0 + y1 pt mod pt+R, y0, y1 Z : 0 y0 pt, 0 y1 pR, (T2.1) y0 (pf 1) (pf 1) mod p, (T2.2) tf f y1 Logp p (p 1) Logp (y0 )(p 1) mod N, (T2.3) x mod p, x Z. (T2.4) Третья глава диссертации посвящена формальному построению ал горитма подъёма решения и другим вспомогательным вопросам, воз никающим в связи с его вычислительной частью. В частности, даются эффективные формулы для вычисления логарифма Артина-Хассе и p адического логарифма. Также приводится алгоритм решения линейного сравнения x mod pM, x Z, возникающего в формулах (Т1.2),(T1.3),(Т2.3).

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

Следущее утверждение дает простое тождество для логарифма Ар тина-Хассе.

Утверждение 3.1. Пусть x – переменная, имеет место сравнение (1 + x)p (1 + xp ) mod pe.

L(1 + x) p Утверждение 3.2 дает полиномиально вычислимое p -адическое при ближение для p -адического логарифма.

Утверждение 3.2. Пусть M N {0}, K, (). Тогда имеет место сравнение M e (1 + )p mod M +1+, Logp (1 + ) M p e где при M, = e 2 1 иначе.

p Наконец, проводится рассчет вычислительной сложности предлага емого алгоритма подъёма решения. При получении оценок растущими параметрами считались лишь p и N.

Теорема 3.5. Cложность алгоритма подъёма решения равна T = O(log3 (pN ) log log(pN )).

В последней, четвертой, главе диссертации строятся новые лога рифмические функции, применение которых приводит к нескратимости сравнений вида (T1.2), (T1.3) и (T2.3).

Предложенные в первой главе функции, логарифм Артина-Хассе и p адический логарифм, обладают неприятным свойством. А именно, срав нения (Т1.2), (Т1.3) и (Т2.3) для любого элемента являются сократи мыми, то есть их левая часть содержится в идеале p. В случае с частны ми Ферма этого эффекта можно было избежать используя их модифика цию, предложенную М.А. Черепневым. В связи с этим возникла задача:

построить логарифмические функции, пригодные к использованию для подъёма решения вместо логарифма Артина-Хассе и p -адического лога рифма, но не обладающие упомянутым свойством. Такие функции были названы оптимальными логарифмическими функциями.

Новые логарифмические функции строятся по аналогии с частными Ферма. Для всех s N рассмотрим множества Us := { Z : ( 1) s}, и для M N, Us определим функции M s ( ) Qs,M () = (2) M где s ( M ) – функция Кармайкла фактор-группы Us /UM, равная по определению НОК порядков образов элементов 1 mod ps в (Z / M ).

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

Лемма 4.2. Пусть, Us, тогда Qs,M () Qs,M () + Qs,M () mod M, то есть отображение Qs,M : (Us, ) (Z / M, +) является гомоморфизмом.

В лемме 4.3 вычисляются значения s ( M ) для некоторых s, M N.

Лемма 4.3. Пусть s, N N.

1. Если s, то N s s ( N ) = p.

e 2. Если s, то s ( sp ) = p.

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

Лемма 4.4. Пусть s, N N.

1. Пусть N s, тогда при UN N s Qs,N () 0 mod e.

e 2. Пусть s, тогда при Usp Qs,sp () 0 mod min{e,sp}.

Лемма 4.5 позволяет подобрать параметры таким образом, чтобы до биться оптимальности построенных функций.

Лемма 4.5. Пусть s, N N, а Us \Us +1, s N, s s.

1. Пусть s, тогда N s + s N.

Qs,N () = e e e 2. Пусть s, тогда s и p e, то (Qs,sp ()) = (s s)p.

(a) Если s p e, то (Qs,sp ()) (s s)p.

(b) Если s = p В конце четвертой главы доказываются формулы, выражающие ло гарифм Артина-Хассе и p -адический логарифм через оптимальные ло гарифмические функции (2).

e Утверждение 4.3. Пусть s N, s и Us \Us+1, а p Us /Usp, тогда найдется ls,sp () Z, такое что (ls,sp ()) = s, и верна формула L() Qs,sp () ls,sp () mod min{e,sp}.

Утверждение 4.4. Пусть M N {0}, а Us, s N, s.

Тогда M s+e e Q s+e M () mod M +1+, Logp () M e s, pe где при M 2, = e 2 1 p1 иначе.

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

Теорема 4.1 Пусть ZK \p, ZK /pN, N N : 1 N pf e 1) N, а t = logp ( N ).

p1 + 1. Пусть также a = ( a Тогда система сравнений i xj pj (pf 1) i f i+ ) L(( 1) ) mod pmin{ap,N }, xi L(p (p ) j= xi Z : 0 xi p, i = 0,..., t 1, эквивалентна системе сравнений i f 1) xi Qapi,api+1 (p (p ) i xj pj (pf 1) i+1 i Qapi,api+1 (( ) mod min{ap,N }ap, ) j= xi Z : 0 xi p, i = 0,..., t 1.

Теорема 4.2 Пусть, ZK \p, N N, N. Обозначим a := tf (p (p 1) 1), где t = logp (pf 1), и пусть a.

Предположим теперь, что x0 Z : 0 x0 pt таково, что вы полнено f f x0 (p 1) (p 1) mod pa, тогда сравнение t f f 1) ) Logp ((x0 )(p 1) x Logp (p (p ) mod N, x Z эквивалентно сравнению t f 1) (p (p ) xQ N a+e e a, f (((x0 )(p 1) )) mod N a, x Z.

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

Автор благодарен заведующему кафедрой, члену-корреспонденту РАН, профессору Ю.В. Нестеренко, и всем сотрудникам кафедры тео рии чисел Механико-математического факультета МГУ за творческую обстановку и доброжелательное отношение.

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ [1] Поповян И.А. Подъём решения показательного сравнения. Матем.

заметки, т. 80 (2006), № 1, c. 76-86.

[2] Поповян И.А. Оптимальные логарифмические функции для подъ ёма решения показательного сравнения. Диск. матем., т. 19 (2007), № 2, с. 53-66.