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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М. В. Ломоносова

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

005054221

ГРЕЧНИКОВ ЕВГЕНИЙ АЛЕКСАНДРОВИЧ

ОЦЕНКИ ЧИСЛА РЕШЕНИЙ ТЕОРЕТИКО-ЧИСЛОВЫХ УРАВНЕНИЙ, ИСПОЛЬЗУЕМЫХ В КРИПТОГРАФИИ

01.01.06 - Математическая логика, алгебра и теория чисел

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

- 1 НОЯ 2012

Москва - 2012

005054221

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

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

доцент Череинёв Михаил Алексеевич

Официальные онноненты: Цфасман Михаил Анатольевич,

доктор физико-математических наук, профессор (Институт проблем передачи инфор- ' мации РАН, заведующий Сектором алгебры и теории чисел)

Осипов Денис Васильевич, кандидат физико-математических наук, старший научный сотрудник (Математический институт им. В. А. Стеклова РАН, отдел алгебры и теории чисел)

Ведущая организация: ФГУП «НИИ Автоматики»

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

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

Автореферат разослан 30 октября 2012 г.

Ученый секретарь диссертационного совета

Д.501.001.84 при МГУ

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

профессор

Иванов Александр Олегович

Общая характеристика работы Актуальность темы

Одной из важных областей теории чисел является изучение конечных полей. Ещё Гаусс доказал, что в иоле вычетов по любому простому модулю существует примитивный элемент д, для которого степени дх при различных целых х пробегают все ненулевые элементы поля. Степени дх можно легко вычислить, но для обратной задачи дискретного логарифмирования — нахождения х по значению дх — неизвестно эффективного алгоритма решения, на чём основаны некоторые криптографические схемы. Это привлекает внимание исследователей к изучению свойств возведения в степень в конечном поле. В частности, известно1, что задача универсальной подделки ГОСТ Р 34.10-94 может быть сведена к решению уравнения

дх = х (mod р), х е {0,... ,р - 1}, (1).

где р — нечётное простое число. Это уравнение можно рассматривать при различных дополнительных ограничениях на g и на х. Хронологически изучение этого уравнения началось с вопроса о существовании решений при каком-либо примитивном д\ этот вопрос получил название проблемы Бризолиса2. Если наложить дополнительное ограничение и рассматривать только примитивные корни х в качестве решений, то их количество асимптотически вычислено в 1995 году3, а также независимо в 1999 году4, что даёт положительный ответ на проблему Бризолиса при всех достаточно больших р. Окончательно (то есть для всех р) проблему Бризолиса решила М. Campbell5 в 2003 году (а именно, такие решения существуют при всех р > 3). М. Campbell не касается вопроса явного построения решений (1); М. А. Черепнёв6 строит конструкции при некоторых ограничениях на р, а также улучшает ранее известные оценки и доказывает существование решений при некоторых g, не являющихся первообразными корнями.

Очевидно, что число решений с примитивными g их даёт нижнюю оценку числа решений при более слабых ограничениях. Гипотетические асимпто- ' тические равенства для чисел решений при различных наборах ограничений выдвинул J. Holden7 в 2002 году. В частности, усреднённое по всем (в том

1 Черепнёв М. А. Криптографические протоколы. Изд-во механико-математического факультета МГУ, 200G.

2 Guy R. К. Unsolved Problems in Number Theory. Springer-Verlag, 1994.

3 Zhang W. P. On a problem of Brizolis // Pure Appl. Math. 1995. Vol. 11. Pp. 1-3.

4 Cobeli C., Zaharescu A. An exponential congruence with solutions in primitive roots // Rev. Roumaine Math. Pures Appl. 1999. Vol. 44. Pp. 15-22.

5 Campbell M. E. On fixed points for discrete logarithms. Master's thesis, University of California at Berkeley, 2003.

6 Черепнёв M. А. Некоторые эффективные оценкн для числа решений задачи Бризолиса // Современные проблемы математики и механики, T.IV «Математика», выпуск 3. Изд-во Московского уииверси-'Х тета. 2009. С. 125-129. . \ •

7 Holden J. Fixed points and two-cycles of the discrete logarithm // ANTS. 2002. Pp. 405-415 'i

числе ненримитивным) g число решений (1) без дополнительных ограничений на х гипотетически есть 1 4- о(1) при р оо. Эта гипотеза оказалась трудной и в общем случае пока не доказана; в 2006 году J. Holden и Р. Могее8 доказали гипотезу для множества р положительной плотности (среди всех ' простых). В 2008 году С. В. Конягин, И. Е. Шиарлинский и Ж. Бургейн9 доказали гипотезу для множества р плотности 1. В ещё не опубликованной работе тех же авторов доказана верхняя оценка 0(1); работа доступна на arxiv.org как arXiv:1103.0567. Усреднённое по примитивным g число решений (1) без дополнительных ограничений на х гипотетически есть также 1 + о(1) при р —> оо.

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

Более конкретно, рассмотрим уравнение

y2 = J{x) (mod р), x,ye¥pJe¥p[x},2]desf. (2)

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

Если / — многочлен третьей степени (свободный от квадратов), то множество решений уравнения (2) вместе с одним «бесконечно удалённым» образует абелеву группу. Рассмотрение всех решений над Fp, а не только над Fp, приводит к эллиптической кривой. Теория эллиптических кривых исключительно обширна; её основы прекрасно изложены в книге J. Silverman10. В частности, неравенство Хассе устанавливает двустороннюю оценку на число решений уравнения (2) для любого возможного / стенени 3 без кратных корней: это число решений (включая «бесконечно удалённое») не может отличаться от р+1 по модулю более чем на Isjp. Теорема Дойринга-Ватерхауза11,12 применительно к полю Fp утверждает, что для любого числа в пределах оценки Хассе существует уравнение вида (2) с таким числом решений.

Операция сложения в группе точек эллиптической кривой легко вычислима. Следовательно, операция умножения точки Р на целое число Р пР, п € Z, также эффективно вычислима. Однако для обратной операции дискретного логарифмирования на эллиптической кривой — вычисления п по

8 Holden J., Могее P. Some heuristics and results for small cycles of the discrete logarithm // Mathematics of computation. 2008. Vol. 75. Pp. 419-449.

9 Bourgain J., Konyagin S. V., Shparlinski I. E. Product sets of rationale, multiplicative translates of subgroups in residue rings, and fixed points of the discrete logarithm // Int. Math. Res. Notices. 2008. No. rnn090

10 Silverman J. H. The Arithmetic of Elliptic Curves. Springer, 1986.

11 Deuring M. Die Typen der Multiplikatorcurmge elliptischer Funktionenkörper // Abh. Math. Sem. Hansischen Univ. 1941. Vol. 14. Pp. 197-272.

12 Waterhouse W. C. Abelian varieties over finite fields // Ann. Sei. École Norm. Sup. 1969. Vol. 2, no. 4. Pp. 521-560.

известным точкам Р и пР — в общем случае неизвестно эффективного алгоритма, на чём основаны некоторые криптографические схемы13,14. Для этих схем важно, чтобы порядок группы точек был простым числом или, по крайней мере, имел большой простой делитель. Кроме того, в некоторых специальных случаях дискретное логарифмирование всё же возможно15'16; их легко запретить дополнительными условиями на порядок группы точек.

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

Друг ой, более эффективный способ построения эллиптических кривых — метод комплексного умножения. Для простых полей первый её вариант описали A. Atkin и F. Morain17 в 1993 году (в качестве вспомогательного средства для алгоритма проверки простоты), для произвольных конечных полей, включая поля характеристики 2, — G.-J. Lay и Н. Zimmer18 в 1994 году. В дальнейшем этот метод неоднократно улучшали19'20,21,22.

Если в уравнении (2) / — многочлен нечётной степени п > 3 (свободный от квадратов), то множество решений этого уравнения над Fp вместе с одним «бесконечно удалённым» есть гинерэллинтическая кривая рода Представим число Fp-точек кривой в виде р + 1 + N, или, что эквивалентно, число ' решений уравнения (2) в виде p + N. Оценка Вешш, доказанная средствами

13 Koblitz N. Elliptic curve cryptosystems 11 Mathematics of Computation. 1987. Vol. 48. Pp. 203-209.

14 Miller V. S. Uses of elliptic curves in cryptography // Advances in Crypt-ology—CRYPTO '85. Vol.

218 of Lecture Notes in Computer Science. Springer-Verlag, 1986. Pp. 417-426.

16 Semaev I. A. Evaluation of discrete logarithm in a group of p-torsion points of an elliptic curve in characteristics p 11 Mathematics of Computation. 1998. Vol. 67. Pp. 353-356.

16 Menezes A. J., Okamoto Т., Vanstone S. A. Reducing elliptic curve logarithms to a finite field // IEEE TVans. Info. Theory. 1993. Vol. 39. Pp. 1639-1646.

17 Atkin A. 0. L., Morain F. Elliptic curves and primality proving // Mathematics of Computation. 1993. Vol. 61, no. 203. Pp. 29-68.

18 Lay G.-J., Zimmer H. G. Constructing elliptic curves with given group order over large finite fields // ANTS / Ed. by L. M. Adleman, M.-D. A. Huang. Vol. 877 of Lecture Notes in Computer Science. Springer, 1994. Pp. 250-263.

19 Enge. A., Morain F. Comparing invariants for class fields of imaginary quadratic fields // Algorithmic Number Theory - ANTS-V (Berlin). Vol. 2369 of Lecture Notes in Computer Science. Springer-Verlag. 2002. Pp. 252-266.

20 Baier. H. Efficient algorithms for generating elliptic curves over finite fields suitable for use in cryptography. Master's thesis, Department of Computer Science, Technical University of Darmstadt, 2002.

21 Enge A., Schertz R. Constructing elliptic curves over finite fields using double eta-quotients // Journal dc Thcorie des Nombrcs rle Bordeaux. 2004. Vol. 16, no. 3. Pp. 555-568.

22 Konstantinou E., Kontogcorgis A., Stamatiou Y. C., Zaroliagis C. D. On the Efficient. Generation of Prime-Order Elliptic Curves // J. Cryptology. 2010. Vol. 23, no. 3. Pp. 477-503.

алгебраической геометрии, утверждает, что \N\ ^ (п — 1)-^. В 1969 году С. А. Степанов23 доказал элементарными методами оценку \N\ ^ \/3пп^/р при р > 9п2. Доказательство основывается на построении ненулевого многочлена не слишком большой степени такого, что все числа х : {^¡^) = 1 являются его корнями достаточно высокой кратности, откуда следует оценка на их количество. Степанов строил такой многочлен как линейную комбинацию с неопределёнными коэффициентами. Позднее, в 1971 году Н. М. Коробов24 построил аналогичный многочлен явным образом, что позволило получить

элементарным методом оценку \N\ < (п — 1 )\Jp — i-"~3H"~4). В 2005 году

Д. А. Митькин25 выдвинул утверждение \N\ < (п — 1)у р — ( ?4("+1), но его доказательство неполное, так как использует лемму из статьи Коробова для значений параметров, не подходящих под ограничения из статьи Коробова.

Цель работы

Цель диссертации — получение новых оценок на количество решений уравнений

дх = х (mod р), х 6 {0,... ,р - 1}, (3)

y2 = f(x) (mod р), х,у eFp,/eFp[®],2tdeg/, (4)

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

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

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

• Получены двусторонние оценки на число решений уравнения (3) в парах • (д,х), где д — первообразный корень по модулю р. В частности, доказано, что в случае, когда имеется растущая последовательность простых р, для которых р— 1 не имеет простых делителей в отрезке ['"^'р2^1^] для фиксированного натурального s, то среднее число решений по всем первообразным д есть 1 + о(1).

• Доказано, что число решений уравнения (4) в парах (х, у) при deg / = 2(7 + 1 отличается от р по модулю менее чем на 2д\]р + 1 — д1.

23 Степанов С. А. О числе точек гиперэллиптической кривой над простым конечным полем // Известия АН СССР. Серия математическая. 1969. Т. 33, X'- 5. С. 1171-1181.

24 Коробов Н. М. Оценка сумм символов Лежандра // Доклады АН СССР. 1971. Т. 196, № 4. С. 764-767.

25 Митькин Д. А. Уточнение оценки для суммы символов Лежандра от многочленов нечётной степени // Чебышевский сборник. 2005. Т. 6, № 3. С. 123-126.

• Получена оценка снизу на максимальное число решений уравнения (4) при с^ / = 5. В частности, показано, что для любого р эта оценка отли- • чается от полученной верхней оценки не более чем на 3. Доказательство содержит конструктивное построение гинерэллиптических кривых рода 2 большого порядка (соответствующих уравнению вида (4) с с^ / = 5) из эллиптических кривых.

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

• Вычислен базис кольца целых ноля родов мнимоквадратичного ноля. Предложен алгоритм построения совместных рациональных приближений к элементам построенного базиса. Доказаны оценки на скорость сходимости типа Дирихле.

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

• Написана программа, которая строит эллиптические кривые с числом точек, равным простому числу вида Софи Жермен.

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

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

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

В диссертации доказываются теоремы и выводятся формулы, которые могут найти применение в алгебраической теории чисел. Построенные алгоритмы с оценками сложности могут использоваться в вычислительной теории чисел. Программа для построения эллиптических кривых на основе резуль-. татов главы 5 диссертации внедрена в НИИ «Автоматики».

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

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

• на научно-исследовательском семинаре кафедры теории чисел (МГУ, Москва, 2011 г.);

• на семинаре «Теоретико-числовые вопросы криптографии» (МГУ, Москва, неоднократно 2008-2010 гг.);

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

• на X международной конференции «Интеллектуальные системы и компьютерные науки» (МГУ, Москва, 2011 г.).

Публикации

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

И, И, [4], [5].

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

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

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

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

Далее записи / = Оа(д) и / <Са д, где f,g — некоторые выражения, а ' — параметр (один или несколько), будут означать существование некоторой константы С = С(а), зависящей от параметра а, такой, что |/| ^ Сд.

Во второй главе доказываются двусторонние оценки для числа решений N(p) уравнения (1) без ограничений но х в среднем но примитивным

91 1

^^й^зуЕК0^^-11^1 (modp)} I-

При а ^ 1 через F(a) обозначим единственный корень уравнения xх = а, не меньший 1. При Ina > 1 выполнено неравенство F(a) ^ асимптотически при а —¥ оо справедлива эквивалентность F(a) ~ ¡¿f^-

Теорема 2.1. Среднее число решений N(p) представляется в виде N(p) = 1 + S(p), где для функции S(p) при произвольном е > 0 справедливы оценки:

• S(j)) > — C(e)p~i+£, где константа С{е) > 0 зависит только от е;

• S(p) ^ exp je" Li и lnp)c '"Inla/J I При достаточно больших p.

Пусть s G N, s > 7. Если число p - 1 не имеет делителей из отрезка [F(p/2),pi], то

S(p) = (^ _

Для доказательства теоремы величина 5(р) представляется в виде некоторой суммы по делителям р - 1. А именно, вводятся функции

Ni(p, d) = |{1 < у ^ р - 1 : (indS0 у,р - 1) = (У,р - 1) =

Р

Связь между S(p) и введёнными функциями описывает следующее утверждение.

Утверждение 2.1. Функцию S(p) можно представить в виде

На различных диапазонах для d для оценки Si(p, d) приходится использовать существенно различные методы. Есть тривиальная нижняя оценка Ni(p, d) ^ 0. Известна1 оценка

нетривиальная при очень больших d. Оценки для меньших d дают следующие утверждения.

Утверждение 2.2. При d < р2/3 и произвольном е > 0 справедлива оценка

iV^p^)«^3/у.

Утверждение 2.3. Существуют такие абсолютные константы с; > 0, что при d > сь р > С2 справедливы следующие оценки.

In In In р

При d ^ р 1п1"р

In In lnp

а при d ^ p lnl"p

Ni(p,d) < c^t^t.

Кроме того, для любого е > 0 и натурального s при d ^ р» выполнена оценка

MM«*,. dk-+s.

Если 2dd < р, то

Nl(p,d) = 0.

1 Campbell М. Е. On fixed points for discrete logarithms. С. 1

Для доказательства последнего утверждения используется следующая лемма, представляющая самостоятельный интерес. Она обобщает хорошо известную2 верхнюю оценку для количества делителей натурального числа: т(п) < ехр {(1 + 1п2} при любом е > 0 и всех достаточно больших п.

Лемма 2.2. Обозначим через Тк,{п) количество представлений натурального числа п в виде произведения к натуральных сомножителей. Для любого е > 0 при всех х ^ жо(е) и 2 ^ к < 1п1пгс справедлива оценка

та.ахтк(п) < ехр {(1 + е). Х 1пк п^х [ 1п 1п х

Результаты второй главы опубликованы в работе [1]. В третьей главе приведено полное доказательство результата, анонсированного Д. А. Митькиным1. А именно, пусть

2=0 4 У '

Тогда число решений уравнения (2) есть р 4- £(/) и справедлива следующая теорема.

Теорема 3.1. При

нечётном п ^ 3, простом р ^ — и многочлене / 6 Ер[х] степени п выполнено неравенство

1ЗД1 < (п - Щ/р - (П"31(П + 1) = (П - 1 )Jp + 1 - -1

Применительно к п = 5 и р > 19 теорема означает следующее. Следствие. При простом р > 19 и многочлене / 6 Гр[а;] степени 5 выполнено неравенство

\S(f)\ < 4Ш+5иР(р), где 6ир(р)

-1, ре {к2 + 1,к2 + 2,к2 + 3},к ем

0, p = k2 + l,3<l^|,keN

1, р = к2 + 1,%<1^к,кеЕ

2, p=k2 + l,k<l^f,keN ■

3, р = к2 + 1,& <l^2k,k€N

Результаты третьей главы опубликованы в работе [3].

В четвёртой главе исследуется вопрос о точности оценки из третьей главы в случае с^ / = 5. Для этого явным образом строятся многочлены / степени 5 с большим числом решений уравнения (2), близким к верхней границе, доказанной в третьей главе. А именно, доказывается следующая теорема.

2 Hardy G. H., Wright Б. М. An introduction to the theory of numbers. Oxford University Press, 1979.

1 Митышн Д. А. Уточнение оценки для суммы... С. 4

Теорема 4.1. Имеет место оценка

max \S(f)\^A[^p\+6down(p), :dcg/=5

где

'-4, р = k2 + l,k eN; Sdownip) = < —2, ре {k2 + 2,k2 + 3},k e N; О, иначе.

Конструкция / основывается на следующей лемме. Лемма 4.1. Пусть ai,a2,b — целые числа, ai ^ a? (mod р),

= S2.

Тогда

(х2 + 2(ai + а2)х + (Д1 - а2)2)2 - 16Ьх2 Р

Si + S2.

Результаты четвёртой главы опубликованы в работе [4].

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

Параграф 5.1, с которого начинается глава, содержит постановку задачи и общий обзор структуры пятой главы.

Параграфы 5.2 и 5.3 содержат краткий обзор используемой теории, а также подробное описание метода комплексного умножения. Для формулировки дальнейших утверждений отметим только, что в методе комплексного умножения вычисляется многочлен

где произведение берётся по некоторому конечному эффективно вычислимому множеству троек, зависящему от параметра D < 0, D = 0,1 (mod 4) и от вида функции в, причём сначала Нв[9] вычисляется приближённо с достаточно высокой точностью, потом точное значение восстанавливается округлением в силу того, что все коэффициенты целые. В базовом варианте метода

Но[в](х)= Д (х-в(А,В,С))е%\х],

(5.1)

(а,в,с)

в различных модификациях функция в может быть другой (возможные варианты описаны в параграфе 5.3), но всегда значение j можно восстановить по известному значению в и многочлен Нц[0] имеет целые коэффициенты.

Буквой D в этой главе всегда обозначается целое число, сравнимое с О или 1 по модулю 4. Для любого такого D существует единственное представление в виде D = df2, где / — натуральное, a d удовлетворяет одному из двух условий:

• либо

d = 1 (mod 4) и d свободно от квадратов, (5.2) '

• либо

d = 0 (mod 4), ^ свободно от квадратов, ^ ф 1 (mod 4).

(5.3)

Лемма 5.2. Пусть d < 0 удовлетворяет одному из условий (5.2) и (5.3). Тогда d люжет быть единственным с точностью до порядка множителей способом представлен в виде произведения

где все попарно взаимно просты, для каждого i либо

q* = (-1 )^qu

для некоторого нечётного простого qi > 0, либо qf € {—4, ±8}.

В параграфе 5.4 рассматривается структура кольца целых Оцс поля родов Kg = ..., y/qf) для поля К = Q(Vd). Сначала найден фундаментальный базис Kg- Затем найдены базисы вещественной и мнимой частей Kg, то есть и /С^ПЖ, которые и будут использованы в дальнейшем. В зависимости от значений д* эти базисы задаются следующими теоремами, в которых используются следующие обозначения.

т^ * •• i+л/й ~ i-x/Sr

Ьсли q* — нечетное число, то положим щ — —f— и а* = —j—.

Группа Галуа Gal(K"c/Q) содержит t элементов Tj, действующих следующим образом:

Tj (v^)= Tj = ^при * ^

Вся группа Галуа исчерпывается автоморфизмами вида Т'и = т^1... г/'' е Ga\(Kc/Q)

при д е {о, 1}'.

Среди д* есть отрицательные числа. Обозначив через и число положительных среди д*, 0 < и < можно без ограничения общности считать, что 1*1 > 0, ..., й > 0, д*+1 < 0, ..., д* < 0. Группа Галуа Са1((К0 П М)/<® состоит из автоморфизмов

= ТА,.....А(_1 = = Т*1 .. . (5.4)

при Л 6 {0,1}'-1, различных при разных Л.

Теорема 5.9. Пусть д^,..., д4* такие же, как в лемлю 5.2, нечётные, занумерованные так, что д* > 0 при 1 ^ г ^ и и д* < 0 при и < г ^ Ь, где и — некоторое число от0доЬ-1 включительно, К а = 0>(\/д[, • • •, \/Щ), тд заданы формулой (5-4). Тогда:

1. Числа

= ^Ь...,5.-1(91, ■ • ■. 0.1) =

когда набор (з{) пробегает всевозможные наборы из {0,образуют фундаментальный базис поля Ко П К.

2. Числа

Ки-л-1 = РИи-л-Ми • • ■ .9«) =

= (й5^"') ((.П^«.1"")(.п^«?).

когда набор (й,) пробегает всевозможные наборы из {0,1}<_1, образуют базис Х-модуля Ока П гМ.

3. Для любых т], V е {0,1}(_1 справедливо равенство

Е (-1Г+-+'"-% .....^л^) =

//6{0Д}'-1

= |(-1 если г, = и,

(0, иначе.

Теорема 5.10. Пусть 4 ^ 2, д2,...,д* такие же, как в теореме 5.9, и д£ = 8. Пусть д* занумерованы так, что д* > 0 при 1^г<иид*<0 при и < г < Ь, где и — некоторое число от 1 до Ь— 1 включительно, Кд = т\ заданы формулой (5.4). Тогда:

11

ßsi..........^(sî,...,?;) = (fl^-*)x

x ГГ П Л «»+( П

\ \f=u+l I \i=u+1 / /

когда набор (si) пробегает всевозможные наборы из {0, l}t_1, образуют фундаментальный базис поля Kg П К.

2. Числа

.Л-, - Ä,.....stJti> ■ • •. 9?) = (-l)51^1"51 (Й ¿^i-5^ X

х ( ( П <* - ( П .

V \t=u+l / \г=ы+1 / /

когда набор (sj) пробегает всевозможные наборы из (О, l}i-1, образуют базис Ъ-модуля <Эка П Ж.

3. Для любых г], и е {О, I}4-1 справедливо равенство

Е ..........Vij =

= v^î... v^f, еслиг1 = и)

1 О, ■ иначе.

Теорема 5.11. Пусть t ^ 2, 9Î, • • • ,?г*_1 такие же, как в теореме 5.9, и q{ £ {-4,-8}. Пусть <?,* занумерованы так, что > 0 при l^i^uu g* < 0 гари и < i ^t, где и — некоторое число от 0 до t — 2 включительно, Kg — Q(y/Öi, ■ ■ ■ i ТА заданы формулой (5.4). Тогда:

1. Числа

Äi.....«-i = А,.....- - -, л/ef) = (П^1-") х

х ( ( П â>i~Si) ( П ^"""f1) at-ii-a*)«-'!

V \<=и+1 / \»=и+1 / /

когда ка^ор (sj) пробегает всевозможные наборы из (О, l}i_1, образуют фундаментальный базис поля К g П R.

12

= К,..«-¿у/Я, ■ ■ • . V?) = (п^1"1)х

X ( - ( П ^(-«О1-"-^ ( П йГ^аА а^о^-'У

когда набор пробегает всевозможные наборы из {О, I}4"1, образуют базис Ъ-модуля Окс П Ж.

3. Для любых г), V е {0,1}<_1 справедливо равенство

Е (-1Г+-+"<-ч (р^.Л^) =

[(- если 77 = I/,

[О, иначе.

Теорема 5.12. Пусть «й,... нечётные положительные, q¡ = —4 или # = -8. Тогда:

1. Числа

«-1

Аг.....= Ль-Л-.^!. ■ • • ,9?) = ПЙ?Ч-_".

«=1

когда набор, (й,) пробегает всевозможные наборы из {0,образуют фундаментальный базис поля Кс П М.

2. Числа

..........9?) = (П5^"") ^

когда набор пробегает всевозможные наборы из {О, I}4-1, образуют базис Ъ-модуля Окс П Ж.

3. Для любых г}, и е {О, I}'-1 справедливо равенство

Е (-1 .....=

/у.е{0,1}'-1

= | если 1] = и,

10, иначе.

В параграфе 5.5 предлагается новая модификация метода комплексного умножения, заключающаяся в использовании вместо многочлена НцЩ его делителя Яд [б]. Напомним, что при определении (5.1) многочлена НвЩ по D определённым образом строится набор троек (А,В,С)\ их всегда можно выбирать так, чтобы gcd(^, D) = 1. Определим на них отображение tp в {±1}' формулой

Ч>{А,В,С) =

где д,*, как и ранее, взяты из леммы 5.2, а (|) — символ Кронекера, мультипликативный по 6, равный символу Лежандра при нечётных простых Ь, для Ь = 2 определённый только в случае о = 0,1 (mod 4) формулой

1, если а = 1 (mod 8), — 1, если а = 5 (mod 8), О, если а = 0 (mod 4).

Теорема 5.13. Образ отображения <р совпадает с группой {(ех,... ,£{) : П!=1 £» = 1} с покомпонентным умножением. На наборе троек (А, В, С) из определения (5.1) можно ввести групповую структуру, относительно которой <р является гомоморфизмом групп.

Определим многочлен НрЩ следующим образом:

Нп[9](х)= П (х-9(А,В,С)).

(а,в,с):р(а,в,с)=( 1.....1)

Аналогично многочлену НоЩ, многочлен легко вычислить по опреде-

лению с любой нанерёд заданной точностью. В отличие от многочлена Нр{9], многочлен НоЩ имеет коэффициенты из Окс, поэтому для его использования в методе комплексного умножения нужно уметь восстанавливать числа из Окс по достаточно точным приближениям.

В параграфе 5.6 вычислена оценка То на все сопряжённые к коэффициентам многочлена НвЩ- Автоморфизмы из группы Галуа Са1(Я'с/(!2) переводят многочлен Нг>[9\ в многочлены вида

Но,пШ*)= П {х-в{А,В,С)).

(А,В,С):р(А,В,С)=ро

Теорема 5.14. Каждый коэффициент, многочлена Но,^а{]\ по модулю не превосходит

ехр |сф + С1Ы (ь2N + 471пN + с* + 1пЛ + '? + 1

< ехр {с^ 1п2 N + с2И 1пЛГ + с3Я + сг 1п N + с4} ,

где N = 7 = 0.577... — константа Эйлера. с\ = \/37г = 5.441...,

с2 = 18.587..., с3 = 17.442..., с4 = 11.594..., с5 = 3.011..., ъ = 2.566... Асимптотическая верхняя оценка

ехр{0(^0|1п2|15|)}

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

В качестве То можно взять оценку из теоремы 5.14, но на практике предла- ■ гается использовать эвристическую, но более точную оценку

1пТ0 ~тгл/Ш1 шах V 4

£б{±1}' А

' (л,в,с):<р(а,в,с)=*е

при использовании инварианта При использовании других функций в следует умножить оценку на где Ф — многочлен от двух переменных, связывающий ] и в, Ф^(г),9(г)) = 0 (такой многочлен существует для всех 9, подходящих для использования в методе комплексного умножения).

Ещё одним необходимым этапом является построение совместных приближений к элементам базиса Кд. Для построения совместных приближений существуют различные универсальные алгоритмы, изучению которых посвящена книга А. ВгепУеэ1. На практике характеристики получаемых приближений существенно различаются для разных алгоритмов, для практических целей, по-видимому, наилучшим является алгоритм скалярных произведений из главы 6А указанной книги. К сожалению, для универсальных алгорит- ■ мов довольно трудно получить теоретические оценки качества. Поэтому в параграфе 5.7 мы предлагаем алгоритм, подходящий только для наборов чисел нужного нам вида, работающий на практике примерно столь же хорошо, сколь и алгоритм скалярных произведений. В том же параграфе мы доказываем для нашего алгоритма оценку качества получаемых приближений, но порядку совпадающего с оценкой теоремы Дирихле.

1 Brentjes A. J. Multi-dimensional continued fraction algorithms. Amsterdam: Mathematisch Centrum,

1981.

Доказательство оценки качества основано на следующей теореме. Основную её часть по существу описал Ь. Реек2, хотя в нашем случае утверждения из этой работы неприменимы. Основные отличия нашей теоремы от работы Ь. Реек заключаются в явной формулировке (в том числе явных константах), введении функции 9Л (Ь. Реек оперирует двойственными базисами, что эквивалентно 9Я = 1) и специализацией для интересующего нас случая (Ь. Реек • не требует нормальности расширения М/ф и описывает также обратную теорему).

Теорема 5.15. Пусть М С Ш — поле такое, что М/(Ц> — расширение Галуа степени т. Пусть У/т и — два <[}-базиса М и

Ш : Са1(М/<ф) —> М — функция (необязательно гомоморфизм) такие, что для всех 1 ^ 1,1' ^ ш выполнено равенство

®t(r)r(HW;) =

reGal(M/Q)

1, если I = I', [ 0, если I ^ V.

Обозначим

с= Y1 |вд^1)1

reGal(M/Q) тфЫ

и при i = 2,..., m Q

Е

T<=Gal(M/Q) тфЫ

ял(т) t{Wi) - Щ

,T(Wi)X

J

Пусть также положительное число А и целые числа Л:,... ,Ат таковы, что

т

1=1 А

Ew

Ч« = 1

si

т

для всех т е Gal(M/Q),r Ф Id.

Тогда:

Справедливо неравенство |Лх| > \ ffl(Id)Wi\Z — С Д.

• Если |Ai| > С А, то Ш(Ы) ^ 0 и при всех i — 2,... ,т справедлива оценка

Л, W,

Лг _ Щ

Ai Wx

|Лх|(

|Ai[-CA \ \WHIQWt\J

2 Peck L. G. Simultaneous rational approximations to algebraic numbers // Bull. Amer. Math. Soc. 19G1. Vol. 67. Pp. 197-201.

Теорема применяется в случае М = Кс ГШ, тп = [М : 0>] = 2'-1, к двум наборам элементов и и*, нумеруемым векторами из {О, I}'-1, образующим базис М над <12 и удовлетворяющим следующим условиям:

1- шо,-,о = 12. Любой элемент кольца целых Ом ноля М разлагается по базису с целыми коэффициентами.

3. Если Л, Л' е {О, I}4-1, то

£ = если':"; (5.5) •

I0' если А ^ А ■

Из теорем параграфа 5.4 следует, что базисы и ¡3* после деления на первый элемент базиса удовлетворяют этим условиям. Более точно, выполнены следующие утверждения. Утверждение. Если

, , __ Д.......н-1

- /30.....о >

и* = ( —....."'-1 /г

ЗЛ(ГД1.....= ^.....

то условия 1-3 выполнены. Утверждение. Если

= (5.7)

.....= ..........о)

то условия 1-3 выполнены.

Для описания алгоритма нам понадобятся следующие величины. Пусть А 6 {О, I}'-1, А ф (0,..., 0). Через © будем обозначать сложение целых чисел по модулю 2. Положим

*А = (9 ^...(^-Ч??)^1®-®^-1. Если чётно, положим

>/Зл

в противном случае положим

1 + %/Зл

9х =

Тогда дх Е Ом-

Поскольку {ш*} образуют <0>-базис ноля М и числа д^ лежат в этом поле,

то в самом начале можно предвычислить такие с^ Е <(2, что

=

Алгоритм построения совместных приближений. Входные данные — набор 5\, дх, введённых выше, а также порог /»/о > 0. Выходные данные

— целые числа Ад такие, что |.Ао,...,о| ^ Щ и для каждого /л Е {0,1}4-1

— приближение к

Алгоритм в процессе работы хранит набор из 2Ь~1 целых чисел Ац, а также вспомогательные наборы целых неотрицательных чисел х\, натуральных чисел (ух, ух) и вещественных положительных чисел (¿д, 5д), где Л € {0,1}г_1, А ф (0,... ,0). Эти наборы имеют некоторый смысл, объяснённый в тексте главы, в терминах ценных дробей к числам д\. Действия алгоритма.

1. Инициализация. Присвоить начальные значения: положить для всех Ае{0,1}<-\ А^(0,...,0)

Л,...,о

Лд

Хх

(г/л, ух)

(гд,2д)

= 1 = о = о

= (1.Ш)

= (1.3а)

У\

2. Итерации. Пока |А),...,о[ < Щ, повторять следующие шаги.

3. Выбрать некоторое А такое, что гд = тах^о,...^) г^.

4. Вычислить а =

5. Присвоить (гх,гх) := (гд - агх,гх).

6. Запомнить х = х\, присвоить хд := ау\-х\ — 4 {&}, после чего присвоить {уХ1 Ух) := {ух ~ а(хх - х),ух). (При этом новое значение хх всегда целое неотрицательное, а новое значение ух натуральное.)

7. Вычислить для всех ц

А' — лм -

Ух

(При этом А'^еЪ для всех ц.) Присвоить А,, := А

Теорема 5.16. Алгоритм завершается за 0(1пЛго) шагов. В процессе работы алгоритма всегда выполнены неравенства

Из теорем 5.15 и 5.16 легко выводится следующее утверждение. Следствие. Алгоритм даёт бесконечную последовательность приближений, для которых верна оценка

Константа в знаке (которую можно выписать явно) зависит от 6, и от выбора базиса ш* и функции ШТ.

Параграф 5.8 завершает описание предлагаемой новой модификации ме-. тода, показывая, как с помощью совместных приближений, вычисленных в параграфе 5.7, и знания оценки всех сопряжённых, вычисленной в параграфе 5.6, можно восстановить точные значения коэффициентов многочлена Нц[в], введённого в параграфе 5.5, в виде разложения по базису, найденному в параграфе 5.4. В конце параграфа приводится общая схема предлагаемой модификации метода комплексного умножения.

Параграф 5.9, завершающий главу, содержит некоторые численные данные по сравнению скорости работы реализации исходного метода и нашей модификации на отрезке 1000000 < |£)| < 1001000. Для случайных дискриминантов время уменьшилось примерно в два раза.

Результаты пятой главы опубликованы в работах [2] и [5].

Автор глубоко благодарен своим научным руководителям за постановку задач и помощь в работе. Устинов Алексей Владимирович, доктор физико-математических наук, привлёк моё внимание к изучению свойств операции х —> <7Х, а также к работам Степанова и Коробова но оценкам числа точек на гииерэллиптических кривых. Михаил Алексеевич Черепнёв, кандидат физико-математических наук, доцент поставил задачу эффективного построения эллиптических кривых с предписанным порядком.

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

0 ^ хх < у/б~\ - дх, 0 < Ух < >Д1\

шах

А и ^и ■ . .1 1

Ч Ао,..,о) Ш(0.....0)

Работы автора по теме диссертации

1. Гречников Е. А. Двусторонние оценки числа неподвижных точек дискретного логарифма // Вестник Московского университета. Серия 1. Математика. Механика. 2012. № 3. С. 3-8.

2. Гречников Е. А. Метод комплексного умножения для построения эллиптических кривых и его оптимизации // Прикладная дискретная математика. 2011. Т. 13, № 3. С. 17-54.

3. Гречников Е. А. Оценка суммы символов Лежандра // Матем. заметки. 2010. Т. 88, № 6. С. 859 866.

4. Гречников Е. А. Суммы символов Лежандра от многочленов степени 5 // Современные проблемы математики и механики, т.1У «Математика», выпуск 3. Изд-во Московского университета. 2009. С. 136-145.

5. Гречников Е. А. Оптимизация метода с комплексным умножением построения эллиптической кривой. 2011. Ден. в ВИНИТИ 21.06.11, № 305-В2011.

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

Глава 1. Введение.

Глава 2. Неподвижные точки дискретного логарифма

2.1. Формулировки.

2.2. Доказательства

2.3. Численные данные.

Глава 3. Верхняя оценка суммы символов Лежандра.

3.1. Формулировки.

3.2. Доказательства.

Глава 4. Построение многочленов степени 5 с большой суммой символов Лежандра.

4.1. Формулировки.

4.2. Доказательства

Глава 5. Построение эллиптических кривых.

5.1. Введение.

5.2. Метод комплексного умножения.

5.3. Свойства изоморфизма Г2.

5.4. Кольцо целых поля родов.

5.5. Делитель многочлена Ноа*] (ж).

5.6. Оценка коэффициентов многочлена Нр[в, а*]

5.7. Построение рациональных приближений к базису кольца целых

5.8. Вычисление элемента поля родов по приближённому значению

5.9. Время работы.

1. Guy R. К. Unsolved Problems in Number Theory. Springer-Verlag, 1994.

2. Zhang W. P. On a problem of Brizolis // Pure Appl. Math. 1995. Vol. 11. P. 1-3.

3. Cobeli C., Zaharescu A. An exponential congruence with solutions in primitive roots // Rev. Roumaine Math. Pures Appl. 1999. Vol. 44. P. 15-22.

4. Campbell M. E. On fixed points for discrete logarithms. Master's thesis, University of California at Berkeley, 2003. URL: http://math.berkeley.edu/~campbell/marithesis.pdf.

5. Череннёв M. А. Некоторые эффективные оценки для числа решений задачи Бризолиса // Современные проблемы математики и механики, t.IV «Математика», выпуск 3. Изд-во Московского университета. 2009. С. 125-129.

6. Черепнёв М. А. Криптографические протоколы. Изд-во механико-математического факультета МГУ, 2006.

7. Holden J. Fixed points and two-cycles of the discrete logarithm // ANTS. 2002. P. 405-415.

8. Holden J., Moree P. Some heuristics and results for small cycles of the discrete logarithm // Mathematics of computation. 2006. Vol. 75. P. 419-449.

9. Bourgain J., Konyagin S. V., Shparlinski I. E. Product sets of rationals, multiplicative translates of subgroups in residue rings, and fixed points of the discrete logarithm // Int. Math. Res. Notices. 2008. no. rnn090.

10. Silverman J. H. The Arithmetic of Elliptic Curves. Springer, 1986.

11. Deuring M. Die Typen der Multiplikatorenringe elliptischer Funktio-nenkorper // Abh. Math. Sem. Hansischen Univ. 1941. Vol. 14. P. 197-272.

12. Waterhouse W. C. Abelian varieties over finite fields // Ann. Sci. Ecole Norm. Sup. 1969. Vol. 2, no. 4. P. 521-560.

13. Koblitz N. Elliptic curve cryptosystems // Mathematics of Computation. 1987. Vol. 48. P. 203-209.

14. Miller V. S. Uses of elliptic curves in cryptography // Advances in Cryp-tology—CRYPTO '85. Vol. 218 of Lecture Notes in Computer Science. Springer-Verlag, 1986. P. 417-426.

15. Atkin A. O. L., Morain F. Elliptic curves and primality proving // Mathematics of Computation. 1993. Vol. 61, no. 203. P. 29-68.

16. Lay G.-J., Zimmer H. G. Constructing elliptic curves with given group order over large finite fields // ANTS / Ed. by L. M. Adleman, M.-D. A. Huang. Vol. 877 of Lecture Notes in Computer Science. Springer, 1994. P. 250-263.

17. Enge A., Morain F. Comparing invariants for class fields of imaginary quadratic fields // Algorithmic Number Theory — ANTS-V (Berlin). Vol. 2369 of Lecture Notes in Computer Science. Springer-Verlag, 2002. P. 252-266.

18. Baier H. Efficient algorithms for generating elliptic curves over finite fields suitable for use in cryptography. Master's thesis, Department of Computer Science, Technical University of Darmstadt, 2002.

19. Enge A., Schertz R. Constructing elliptic curves over finite fields using double eta-quotients // Journal de Theorie des Nombres de Bordeaux. 2004. Vol. 16, no. 3. P. 555-568.

20. Konstantinou E., Kontogeorgis A., Stamatiou Y. C., Zaroliagis C. D. On the Efficient Generation of Prime-Order Elliptic Curves //J. Cryptology. 2010. Vol. 23, no. 3. P. 477-503.

21. Степанов С. А. О числе точек гиперэллиптической кривой над простым конечным полем // Известия АН СССР. Серия математическая. 1969. Т. 33, № 5. С. 1171-1181.

22. Коробов Н. М. Оценка сумм символов Лежандра // Доклады АН СССР. 1971. Т. 196, № 4. С. 764-767.

23. Митькин Д. А. Уточнение оценки для суммы символов Лежандра от многочленов нечётной степени // Чебышевский сборник. 2005. Т. 6, № 3. С. 123-126.

24. Черепнёв М. А. Криптографические протоколы. М.: МГУ, 2006.

25. Konyagin S. V., Shparlinski I. E. Character sums with exponential functions and their applications. Cambridge University Press, 1999.

26. Hardy G. H., Wright E. M. An introduction to the theory of numbers. Oxford University Press, 1979.

27. Ramanujan S. Highly composite numbers. Annotated and with a foreword by Jean-Louis Nicolas and Guy Robin // Ramanujan J. 1997. Vol. 1, no. 2. P. 119-153.

28. Weil A. Sur les courbes algébriques et les variétés qui s'en déduisent. Paris: Hermann et Cie., 1948.

29. Weil A. Variétés abéliennes et courbes algébriques. Paris: Hermann et Cie., 1948.

30. Serre J.-P. Sur le nombre des points rationnels d'une courbe algébrique sur un corps fini // C.R. Acad. Sei. Paris Sér. I Math. 1983. Vol. 296. P. 397-402.

31. Brewer В. W. On certain character sums // Trans. Amer. Math. Soc. 1961. Vol. 99. P. 241-245.

32. Lenstra H. W. Factoring integers with elliptic curves // Annals of Mathematics. 1987. Vol. 126. P. 649-673.

33. Cox D. A. Primes of the form x2 + ny2. New York: Wiley, 1989.

34. Weber H. Lehrbuch der Algebra. 3rd edition. New York: Chelsea Publishing Company, 1908. Vol. 3.

35. Ленг С. Эллиптические функции. Москва: Наука, Главная редакция физико-математической литературы, 1984.

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

37. Cornacchia G. Su di un metodo per la risoluzione in numeri interi dell' equazione Y^h=vCh,xn~hyh = P // Giornale di Matematiche di Battaglini. 1908. no. 46. P. 33-90.

38. Schertz R. Weber's class invariants revisited // Journal de Theorie des Nombres de Bordeaux. 2002. Vol. 14, no. 1. P. 325-343.

39. Cohn H. Introduction to the construction of class fields. Cambridge University Press, 1985.

40. Ленг С. Алгебраические числа. М.: Мир, 1966.

41. Enge A. The complexity of class polynomial computation via floating point approximations // Mathematics of Computation. 2009. Vol. 78, no. 266. P. 1089-1107.

42. Brisebarre N., Philibert G. Effective lower and upper bounds for the Fourier coefficients of powers of the modular invariant j // Journal of the Ramanujan Mathematical Society. 2005. Vol. 20. P. 255-282.

43. Brentjes A. J. Multi-dimensional continued fraction algorithms. Amsterdam: Mathematisch Centrum, 1981.

44. Peck L. G. Simultaneous rational approximations to algebraic numbers // Bull. Amer. Math. Soc. 1961. Vol. 67. P. 197-201.

45. Хинчин А. Я. Цепные дроби. M.: Наука, 1978.

46. Венков Б. А. Элементарная теория чисел. ОНТИ НКТП СССР, 1937.

47. Enge A. The CM software, 0.1 edition. 2009. URL: http://www.multiprecision.org/index.php?prog=cm&page=home.

48. LiDIA-Group. LiDlA — A library for computational number theory. 2001. URL: http://www.cdc.informatik.tu-darmstadt.de/TI/LiDIA/.Работы автора по теме диссертации

49. Гречников Е. А. Двусторонние оценки числа неподвижных точек дискретного логарифма // Вестник Московского университета. Серия 1. Математика. Механика. 2012. № 3. С. 3-8.

50. Гречников Е. А. Метод комплексного умножения для построения эллиптических кривых и его оптимизации // Прикладная дискретная математика. 2011. Т. 13, № 3. С. 17-54.

51. Гречников Е. А. Оценка суммы символов Лежандра // Матем. заметки. 2010. Т. 88, № 6. С. 859-866.

52. Гречников Е. А. Суммы символов Лежандра от многочленов степени 5 // Современные проблемы математики и механики, t.IV «Математика», выпуск 3. Изд-во Московского университета. 2009. С. 136-145.