close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
ФИО соискателя: Гречников Евгений Александрович Шифр научной специальности: 01.01.06 - математическая логика, алгебра и теория чисел Шифр диссертационного совета: Д 501.001.84 Название организации: Московский государственный университет им.М.В.Ломон
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
им. М. В. Ломоносова
На правах рукописи
ГРЕЧНИКОВ ЕВГЕНИЙ АЛЕКСАНДРОВИЧ
ОЦЕНКИ ЧИСЛА РЕШЕНИЙ
ТЕОРЕТИКО-ЧИСЛОВЫХ
УРАВНЕНИЙ, ИСПОЛЬЗУЕМЫХ В
КРИПТОГРАФИИ
01.01.06 – Математическая логика, алгебра и теория чисел
АВТОРЕФЕРАТ
диссертации на соискание ученой степени
кандидата физико-математических наук
Москва – 2012
Работа выполнена на кафедре теории чисел Механико-математического
факультета Московского государственного университета имени
М. В. Ломоносова.
Научный руководитель:
кандидат физико-математических наук,
доцент Черепнёв Михаил Алексеевич
Официальные оппоненты: Цфасман Михаил Анатольевич,
доктор физико-математических наук,
профессор (Институт проблем передачи инфор­
мации РАН, заведующий Сектором алгебры и
теории чисел)
Осипов Денис Васильевич,
кандидат физико-математических наук,
старший научный сотрудник (Математический
институт им. В. А. Стеклова РАН, отдел алгеб­
ры и теории чисел)
Ведущая организация:
ФГУП «НИИ Автоматики»
Защита диссертации состоится 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)
где  — нечётное простое число. Это уравнение можно рассматривать при раз­
личных дополнительных ограничениях на  и на . Хронологически изучение
этого уравнения началось с вопроса о существовании решений при каком­
либо примитивном ; этот вопрос получил название проблемы Бризолиса2 .
Если наложить дополнительное ограничение и рассматривать только прими­
тивные корни  в качестве решений, то их количество асимптотически вычис­
лено в 1995 году3 , а также независимо в 1999 году4 , что даёт положительный
ответ на проблему Бризолиса при всех достаточно больших . Окончательно
(то есть для всех ) проблему Бризолиса решила M. Campbell5 в 2003 году (а
именно, такие решения существуют при всех  > 3). M. Campbell не касается
вопроса явного построения решений (1); М. А. Черепнёв6 строит конструкции
при некоторых ограничениях на , а также улучшает ранее известные оцен­
ки и доказывает существование решений при некоторых , не являющихся
первообразными корнями.
Очевидно, что число решений с примитивными  и  даёт нижнюю оцен­
ку числа решений при более слабых ограничениях. Гипотетические асимпто­
тические равенства для чисел решений при различных наборах ограничений
выдвинул J. Holden7 в 2002 году. В частности, усреднённое по всем (в том
1
Черепнёв М. А. Криптографические протоколы. Изд-во механико-математического факультета
МГУ, 2006.
2
Guy R. K. 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
Черепнёв М. А. Некоторые эффективные оценки для числа решений задачи Бризолиса // Совре­
менные проблемы математики и механики, т.IV «Математика», выпуск 3. Изд-во Московского универси­
тета. 2009. С. 125–129.
7
Holden J. Fixed points and two-cycles of the discrete logarithm // ANTS. 2002. Pp. 405–415
1
числе непримитивным)  число решений (1) без дополнительных ограниче­
ний на  гипотетически есть 1 + (1) при  → ∞. Эта гипотеза оказалась
трудной и в общем случае пока не доказана; в 2006 году J. Holden и P. Moree8
доказали гипотезу для множества  положительной плотности (среди всех
простых). В 2008 году C. В. Конягин, И. Е. Шпарлинский и Ж. Бургейн9
доказали гипотезу для множества  плотности 1. В ещё не опубликованной
работе тех же авторов доказана верхняя оценка (1); работа доступна на
arxiv.org как arXiv:1103.0567. Усреднённое по примитивным  число решений
(1) без дополнительных ограничений на  гипотетически есть также 1 + (1)
при  → ∞.
Другим важным объектом в теории конечных полей являются уравнения
от двух переменных, задаваемые многочленами. Здесь теория чисел тесно
связана с алгебраической геометрией.
Более конкретно, рассмотрим уравнение
 2 ≡  ()
(mod ),
,  ∈ F ,  ∈ F [], 2 deg .
(2)
Если многочлен  делится на квадрат какого-либо многочлена, то это урав­
нение очевидной заменой переменных сводится к уравнению того же вида с
многочленом меньшей степени. Далее будем считать, что  свободен от квад­
ратов.
Если  — многочлен третьей степени (свободный от квадратов), то мно­
жество решений уравнения (2) вместе с одним «бесконечно удалённым» обра­
зует абелеву группу. Рассмотрение всех решений над F , а не только над F ,
приводит к эллиптической кривой. Теория эллиптических кривых исключи­
тельно обширна; её основы прекрасно изложены в книге J. Silverman10 . В част­
ности, неравенство Хассе устанавливает двустороннюю оценку на число реше­
ний уравнения (2) для любого возможного  степени 3 без кратных корней:
это число решений (включая «бесконечно удалённое») не может отличаться
√
от  + 1 по модулю более чем на 2 . Теорема Дойринга–Ватерхауза11,12 при­
менительно к полю F утверждает, что для любого числа в пределах оценки
Хассе существует уравнение вида (2) с таким числом решений.
Операция сложения в группе точек эллиптической кривой легко вычис­
лима. Следовательно, операция умножения точки  на целое число  ↦→  ,
 ∈ Z, также эффективно вычислима. Однако для обратной операции дис­
кретного логарифмирования на эллиптической кривой — вычисления  по
8
Holden J., Moree P. Some heuristics and results for small cycles of the discrete logarithm // Mathematics
of computation. 2006. Vol. 75. Pp. 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 Funktionenk¨orper // Abh. Math. Sem.
Hansischen Univ. 1941. Vol. 14. Pp. 197–272.
12
`
Waterhouse W. C. Abelian varieties over finite fields // Ann. Sci. Ecole
Norm. Sup. 1969. Vol. 2, no.
4. Pp. 521–560.
2
известным точкам  и  — в общем случае неизвестно эффективного алго­
ритма, на чём основаны некоторые криптографические схемы13,14 . Для этих
схем важно, чтобы порядок группы точек был простым числом или, по край­
ней мере, имел большой простой делитель. Кроме того, в некоторых специаль­
ных случаях дискретное логарифмирование всё же возможно15,16 ; их легко
запретить дополнительными условиями на порядок группы точек.
Теорема Дойринга–Ватерхауза гарантирует существование эллиптической
кривой с нужным порядком, но не содержит способа построения такой кри­
вой. Один из возможных методов построения — случайно выбирать коэффи­
циенты уравнения кривой и подсчитывать число точек с помощью алгоритма
Шуфа в цикле, пока вычисленное число точек не удовлетворяет заданным
условиям. Следует отметить, что вероятность случайно получить кривую с
порядком, делящимся на большое простое число, не слишком велика. Кроме
того, сложность алгоритма Шуфа хотя и полиномиальна (по размеру вход­
ных данных), но растёт достаточно быстро.
Другой, более эффективный способ построения эллиптических кривых
— метод комплексного умножения. Для простых полей первый её вариант
описали A. Atkin и F. Morain17 в 1993 году (в качестве вспомогательного
средства для алгоритма проверки простоты), для произвольных конечных
полей, включая поля характеристики 2, — G.-J. Lay и H. Zimmer18 в 1994
году. В дальнейшем этот метод неоднократно улучшали19,20,21,22 .
Если в уравнении (2)  — многочлен нечётной степени  > 3 (свободный
от квадратов), то множество решений этого уравнения над F вместе с одним
«бесконечно удалённым» есть гиперэллиптическая кривая рода −1
2 . Предста­
вим число F -точек кривой в виде  + 1 +  , или, что эквивалентно, число
решений уравнения (2) в виде  +  . Оценка Вейля, доказанная средствами
13
Koblitz N. Elliptic curve cryptosystems // Mathematics of Computation. 1987. Vol. 48. Pp. 203–209.
Miller V. S. Uses of elliptic curves in cryptography // Advances in Cryptology—CRYPTO ’85. Vol.
218 of Lecture Notes in Computer Science. Springer-Verlag, 1986. Pp. 417-426.
15
Semaev I. A. Evaluation of discrete logarithm in a group of -torsion points of an elliptic curve in
characteristics  // Mathematics of Computation. 1998. Vol. 67. Pp. 353–356.
16
Menezes A. J., Okamoto T., Vanstone S. A. Reducing elliptic curve logarithms to a finite field // IEEE
Trans. Info. Theory. 1993. Vol. 39. Pp. 1639–1646.
17
Atkin A. O. 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
de Th´eorie des Nombres de Bordeaux. 2004. Vol. 16, no. 3. Pp. 555–568.
22
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. Pp. 477–503.
14
3
√
алгебраической геометрии, утверждает, что | |
( − 1) . В 1969
году
√
√
С. А. Степанов23 доказал элементарными методами оценку | |
3 
при  > 92 . Доказательство основывается на построении ненулевого
много­
(︁
)︁
 ()
члена не слишком большой степени такого, что все числа  :  = 1 явля­
ются его корнями достаточно высокой кратности, откуда следует оценка на
их количество. Степанов строил такой многочлен как линейную комбинацию
с неопределёнными коэффициентами. Позднее, в 1971 году Н. М. Коробов24
построил аналогичный многочлен явным образом,
√︁ что позволило получить
( − 1)  −
элементарным методом оценку | |
(−3)(−4)
.
√︁ 4
В 2005 году
Д. А. Митькин25 выдвинул утверждение | | ( − 1)  − (−3)(+1)
, но его
4
доказательство неполное, так как использует лемму из статьи Коробова для
значений параметров, не подходящих под ограничения из статьи Коробова.
Цель работы
Цель диссертации — получение новых оценок на количество решений
уравнений
  ≡  (mod ),  ∈ {0, . . . ,  − 1},
(3)
 2 ≡  ()
(mod ),
,  ∈ F ,  ∈ F [], 2 deg ,
(4)
где  — простое нечётное, а также оптимизация построения эллиптических
кривых, для которых соответствующее уравнение вида (4) имеет число реше­
ний с предписанными свойствами.
Научная новизна
Результаты диссертации являются новыми и состоят в следующем:
∙ Получены двусторонние оценки на число решений уравнения (3) в парах
(, ), где  — первообразный корень по модулю . В частности, доказа­
но, что в случае, когда имеется растущая последовательность простых
2 1/
, для которых  − 1 не имеет простых делителей в отрезке [ lnln−ln
]
ln  , 
для фиксированного натурального , то среднее число решений по всем
первообразным  есть 1 + (1).
∙ Доказано, что число решений уравнения (4) в парах
√︀ (, ) при deg  =
2 + 1 отличается от  по модулю менее чем на 2  + 1 −  2 .
23
Степанов С. А. О числе точек гиперэллиптической кривой над простым конечным полем //
Известия АН СССР. Серия математическая. 1969. Т. 33, № 5. С. 1171–1181.
24
Коробов Н. М. Оценка сумм символов Лежандра // Доклады АН СССР. 1971. Т. 196, № 4. С.
764–767.
25
Митькин Д. А. Уточнение оценки для суммы символов Лежандра от многочленов нечётной сте­
пени // Чебышевский сборник. 2005. Т. 6, № 3. С. 123–126.
4
∙ Получена оценка снизу на максимальное число решений уравнения (4)
при deg  = 5. В частности, показано, что для любого  эта оценка отли­
чается от полученной верхней оценки не более чем на 3. Доказательство
содержит конструктивное построение гиперэллиптических кривых рода
2 большого порядка (соответствующих уравнению вида (4) с deg  = 5)
из эллиптических кривых.
∙ Предложена новая модификация метода построения эллиптических кри­
вых, использующего комплексное умножение. Показано, что можно эф­
фективно использовать делитель многочлена Гильберта с коэффициен­
тами, являющимися целыми в поле родов мнимоквадратичного поля.
∙ Вычислен базис кольца целых поля родов мнимоквадратичного поля.
Предложен алгоритм построения совместных рациональных приближе­
ний к элементам построенного базиса. Доказаны оценки на скорость
сходимости типа Дирихле.
∙ Предложен алгоритм восстановления точных значений коэффициентов
разложения целого алгебраического числа из поля родов мнимоквадра­
тичного поля по приближённому значению числа и оценке модуля всех
сопряжённых к нему.
∙ Написана программа, которая строит эллиптические кривые с числом
точек, равным простому числу вида Софи Жермен.
Основные методы исследования
В диссертации используются методы из алгебраической и алгоритмиче­
ской теории чисел.
Теоретическая и практическая ценность
В диссертации доказываются теоремы и выводятся формулы, которые
могут найти применение в алгебраической теории чисел. Построенные алго­
ритмы с оценками сложности могут использоваться в вычислительной теории
чисел. Программа для построения эллиптических кривых на основе резуль­
татов главы 5 диссертации внедрена в НИИ «Автоматики».
Апробация работы
Результаты диссертации докладывались автором на следующих научных
семинарах и конференциях:
∙ на научно-исследовательском семинаре кафедры теории чисел (МГУ,
Москва, 2011 г.);
5
∙ на семинаре «Теоретико-числовые вопросы криптографии» (МГУ, Москва,
неоднократно 2008–2010 гг.);
∙ на конференции «Ломоносовские чтения» (МГУ, Москва, 2009 г.);
∙ на X международной конференции «Интеллектуальные системы и ком­
пьютерные науки» (МГУ, Москва, 2011 г.).
Публикации
Результаты автора по теме диссертации опубликованы в 5 работах [1],
[2], [3], [4], [5].
Структура и объём диссертации
Диссертация состоит из введения, четырёх глав и библиографии (54 на­
именований). Общий объём диссертации составляет 113 страниц.
Содержание работы
Во введении, являющемся первой главой, описывается структура
диссертации; обосновывается актуальность темы и научная новизна получен­
ных результатов; излагаются основные результаты диссертации.
Далее записи  =  () и  ≪ , где ,  — некоторые выражения, 
— параметр (один или несколько), будут означать существование некоторой
константы  = (), зависящей от параметра , такой, что | | .
Во второй главе доказываются двусторонние оценки для числа реше­
ний  () уравнения (1) без ограничений по  в среднем по примитивным
:
∑︁ ⃒
⃒
1
⃒{0   − 1 :   ≡  (mod )}⃒.
 () =
( − 1) 
При  1 через  () обозначим единственный корень уравнения  = , не
ln 
меньший 1. При ln  > 1 выполнено неравенство  ()
ln ln  , асимптотиче­
ски при  → ∞ справедлива эквивалентность  () ∼ lnlnln .
Теорема 2.1. Среднее число решений  () представляется в виде  () =
1 + (), где для функции () при произвольном  > 0 справедливы оценки:
∙ ()
∙ ()
1
−()− 4 + , где константа () > 0 зависит только от ;
{︁
(︁
)︁}︁
 lnlnlnlnlnlnln
′
exp  Li (ln )
при достаточно больших .
6
Пусть  ∈ N, 
1
[ (/2),   ], то
7. Если число  − 1 не имеет делителей из отрезка
(︁
() = , 
1
− 1 + (−1)
+
)︁
.
Для доказательства теоремы величина () представляется в виде некоторой
суммы по делителям  − 1. А именно, вводятся функции
⃒
1 (, ) = ⃒{1

 − 1 ⃒⃒
−1
, (,  − 1) =
},


 − 1 : (ind0 ,  − 1) =
2 ()
1 (, ) = 1 (, ) −
.

Связь между () и введёнными функциями описывает следующее утвержде­
ние.
Утверждение 2.1. Функцию () можно представить в виде
() =
∑︁ 1 (, ) 1
− .
()

|−1
На различных диапазонах для  для оценки 1 (, ) приходится использовать
существенно различные методы. Есть тривиальная нижняя оценка 1 (, )
0. Известна1 оценка
1
|1 (, )| ≪  2 + ,
нетривиальная при очень больших . Оценки для меньших  дают следующие
утверждения.
Утверждение 2.2. При  < 2/3 и произвольном  > 0 справедлива оценка
1 (, ) ≪ 3/4  .
Утверждение 2.3. Существуют такие абсолютные константы  > 0,
что при  > 1 ,  > 2 справедливы следующие оценки.
ln ln ln 
При   ln ln 
ln 
1 (, ) 3 ln  ,
а при 

ln ln ln 
ln ln 
4
1 (, )
ln ln ln 
ln ln 
.
Кроме того, для любого  > 0 и натурального  при 
оценка
1
1 (, ) ≪,   + .
Если 2 < , то
1 (, ) = 0.
1
Campbell M. E. On fixed points for discrete logarithms. С. 1
7
1
  выполнена
Для доказательства последнего утверждения используется следующая лем­
ма, представляющая самостоятельный интерес. Она обобщает хорошо извест­
2
ную{︀
верхнюю оценку
}︀ для количества делителей натурального числа:  () <
ln 
exp (1 + ) ln ln  ln 2 при любом  > 0 и всех достаточно больших .
Лемма 2.2. Обозначим через  () количество представлений натурально­
го числа  в виде произведения  натуральных сомножителей. Для любого
 > 0 при всех  0 () и 2  ln ln  справедлива оценка
}︂
{︂
ln 
ln  .
max  () exp (1 + )
 
ln ln 
Результаты второй главы опубликованы в работе [1].
В третьей главе приведено полное доказательство результата, анонси­
рованного Д. А. Митькиным1 . А именно, пусть
)︂
−1 (︂
∑︁
 ()
( ) =
.

=0
Тогда число решений уравнения (2) есть  + ( ) и справедлива следующая
теорема.
2
 −1
Теорема 3.1. При нечётном 
3, простом 
и многочлене  ∈
2
F [] степени  выполнено неравенство
√︃
√︂
)︂2
(︂
( − 3)( + 1)
−1
= ( − 1)  + 1 −
.
|( )| < ( − 1)  −
4
2
Применительно к  = 5 и  > 19 теорема означает следующее.
Следствие. При простом  > 19 и многочлене  ∈ F [] степени 5 выполнено
неравенство
⎧
⎪
−1,  ∈ { 2 + 1,  2 + 2,  2 + 3},  ∈ N
⎪
⎪
⎪
⎪
⎪
0,
 =  2 + , 3 <  2 ,  ∈ N
⎨
√
|( )| 4[ ]+ (), где  () = 1,
 =  2 + , 2 <  ,  ∈ N
⎪
⎪
⎪
2,
 =  2 + ,  <  3
⎪
2 , ∈ N
⎪
⎪
⎩3,
3
2
 =  + , 2 <  2,  ∈ N
Результаты третьей главы опубликованы в работе [3].
В четвёртой главе исследуется вопрос о точности оценки из третьей
главы в случае deg  = 5. Для этого явным образом строятся многочлены
 степени 5 с большим числом решений уравнения (2), близким к верхней
границе, доказанной в третьей главе. А именно, доказывается следующая
теорема.
2
1
Hardy G. H., Wright E. M. An introduction to the theory of numbers. Oxford University Press, 1979.
Митькин Д. А. Уточнение оценки для суммы... С. 4
8
Теорема 4.1. Имеет место оценка
max |( )|
 :deg  =5
где
√
4[ ] +  (),
⎧
2
⎪
⎨−4,  =  + 1,  ∈ N;
 () = −2,  ∈ { 2 + 2,  2 + 3},  ∈ N;
⎪
⎩0,
иначе.
Конструкция  основывается на следующей лемме.
Лемма 4.1. Пусть 1 , 2 ,  — целые числа, 1 ̸≡ 2 (mod ),
)︂ (︂ 2
)︂
)︂ (︂ 2
)︂
−1 (︂
−1 (︂
∑︁
∑︁
 − 1
 −
 − 2
 −
= 1 ,
= 2 .




=0
=0
Тогда
−1 (︂ )︂
∑︁

=0

(︃ (︀
2 + 2(1 + 2 ) + (1 − 2 )2

)︀2
− 162
)︃
= 1 + 2 .
Результаты четвёртой главы опубликованы в работе [4].
В пятой главе рассматривается построение эллиптических кривых над
конечным полем с предписанным порядком. В отличие от предыдущих глав,
здесь рассматривается произвольное конечное поле F , не обязательно про­
стое поле F ; это связано с тем, что на практике иногда используются эл­
липтические кривые над полем F2 , поскольку при программной реализации
некоторые операции в таком поле более эффективны.
Параграф 5.1, с которого начинается глава, содержит постановку задачи
и общий обзор структуры пятой главы.
Параграфы 5.2 и 5.3 содержат краткий обзор используемой теории, а
также подробное описание метода комплексного умножения. Для формули­
ровки дальнейших утверждений отметим только, что в методе комплексного
умножения вычисляется многочлен
∏︁
 []() =
( − (, , )) ∈ Z[],
(5.1)
(,,)
где произведение берётся по некоторому конечному эффективно вычислимо­
му множеству троек, зависящему от параметра  < 0,  ≡ 0, 1 (mod 4) и
от вида функции , причём сначала  [] вычисляется приближённо с доста­
точно высокой точностью, потом точное значение восстанавливается округле­
нием в силу того, что все коэффициенты целые. В базовом варианте метода
(︃
√ )︃
− + 
(, , ) = 
,
2
9
в различных модификациях функция  может быть другой (возможные ва­
рианты описаны в параграфе 5.3), но всегда значение  можно восстановить
по известному значению  и многочлен  [] имеет целые коэффициенты.
Буквой  в этой главе всегда обозначается целое число, сравнимое с 0
или 1 по модулю 4. Для любого такого  существует единственное представ­
ление в виде  =  2 , где  — натуральное, а  удовлетворяет одному из двух
условий:
∙ либо
≡1
(mod 4) и  свободно от квадратов,
(5.2)
∙ либо
≡0
(mod 4),

свободно от квадратов,
4

̸≡ 1
4
(mod 4).
(5.3)
Лемма 5.2. Пусть  < 0 удовлетворяет одному из условий (5.2) и (5.3).
Тогда  может быть единственным с точностью до порядка множителей
способом представлен в виде произведения
 = 1* . . . * ,
где все * попарно взаимно просты, для каждого  либо
* = (−1)
 −1
2
 ,
для некоторого нечётного простого  > 0, либо * ∈ {−4, ±8}.
В параграфе
структура
√кольца целых  поля ро­
√︀ *
√︀ *5.4 рассматривается
дов  = ( 1 , . . . ,  ) для поля  = Q( ). Сначала найден фунда­
ментальный базис  . Затем найдены базисы вещественной и мнимой частей
 , то есть  ∩ R и  ∩ R, которые и будут использованы в дальнейшем.
В зависимости от значений * эти базисы задаются следующими теоремами,
в которых используются следующие обозначения. √
√
1+
*
1−
*
˜ = 2  .
Если * — нечётное число, то положим  = 2  и 
Группа Галуа Gal( /Q) содержит  элементов  , действующих следу­
ющим образом:
(︁√︁ )︁
(︁√︀ )︁ √︀
√︁
*
*

 = −  , 
* = * при  ̸= .
Вся группа Галуа исчерпывается автоморфизмами вида
′ = 11 . . .  ∈ Gal( /Q)
при  ∈ {0, 1} .
10
Среди * есть отрицательные числа. Обозначив через  число положи­
тельных среди * , 0  < , можно без ограничения общности считать, что
*
< 0, . . . , * < 0. Группа Галуа Gal(( ∩ R)/Q)
1* > 0, . . . , * > 0, +1
состоит из автоморфизмов

−1
 = 1 ,...,−1 = ′ 1 ,...,−1 ,0 = 11 . . . −1
(5.4)
при  ∈ {0, 1}−1 , различных при разных .
Теорема 5.9. Пусть 1* , . . . , * такие же, как в лемме 5.2, нечётные, зану­
мерованные так, что * > 0 при 1

 и * < 0 при√︀ <  √︀
, где 
*
— некоторое число от 0 до  − 1 включительно,  = Q( 1 , . . . , * ), 
заданы формулой (5.4). Тогда:
1. Числа
1 ,...,−1 = 1 ,...,−1 (1* , . . . , * ) =
(︃ 
)︃ (︃(︃ −1
)︃
(︃ −1
)︃ )︃
∏︁
∏︁
∏︁
=

˜  1−

˜  1−  +

˜ 1−  
˜ ,
=1
=+1
=+1
когда набор ( ) пробегает всевозможные наборы из {0, 1}−1 , образуют
фундаментальный базис поля  ∩ R.
2. Числа
*1 ,...,−1 = *1 ,...,−1 (1* , . . . , * ) =
(︃ 
)︃ (︃(︃ −1
)︃
(︃ −1
)︃ )︃
∏︁
∏︁
∏︁
=

˜  1−

˜  1−  −

˜ 1−  
˜ ,
=1
=+1
=+1
когда набор ( ) пробегает всевозможные наборы из {0, 1}−1 , образуют
базис Z-модуля  ∩ R.
3. Для любых ,  ∈ {0, 1}−1 справедливо равенство
∑︁
(︀
)︀
(−1)1 +...+−1  1 ,...,−1 *1 ,...,−1 =
∈{0,1}−1
{︃
√︀
√︀
(−1)1 +...+−1 1* . . . * ,
=
0,
если  = ,
иначе.
Теорема 5.10. Пусть 
2, 2* , . . . , * такие же, как в теореме 5.9, и
1* = 8. Пусть * занумерованы так, что * > 0 при 1

 и * < 0
при√︀ <  √︀
, где  — некоторое число от 1 до  − 1 включительно,  =
*
Q( 1 , . . . , * ),  заданы формулой (5.4). Тогда:
11
1. Числа
1 ,...,−1 = 1 ,...,−1 (1* , . . . , * ) =
(︃(︃
×
−1
∏︁
√
2
1
(︃

∏︁
)︃

˜  1−
=2
)︃

˜  1−
(︃
)︃
−1
∏︁
 +
=+1
×

˜ 1− 
)︃

˜ ,
=+1
когда набор ( ) пробегает всевозможные наборы из {0, 1}−1 , образуют
фундаментальный базис поля  ∩ R.
2. Числа
√
1−1
(︃
*1 ,...,−1 = *1 ,...,−1 (1* , . . . , * ) = (−1)1 2
(︃(︃
×
−1
∏︁
)︃

˜  1−
 −
=+1

∏︁
)︃

˜  1−
(︃=2−1
∏︁
×
)︃

˜ 1− 
)︃

˜ ,
=+1
когда набор ( ) пробегает всевозможные наборы из {0, 1}−1 , образуют
базис Z-модуля  ∩ R.
3. Для любых ,  ∈ {0, 1}−1 справедливо равенство
∑︁
(︀
)︀
(−1)1 +...+−1  1 ,...,−1 *1 ,...,−1 =
∈{0,1}−1
{︃
√︀
√︀
(−1)1 +...+−1 1* . . . * ,
=
0,
если  = ,
иначе.
*
Теорема 5.11. Пусть 
2, 1* , . . . , −1
такие же, как в теореме 5.9, и
*
*

 и
 ∈ {−4, −8}. Пусть  занумерованы так, что * > 0 при 1
*
 < 0 при
√︀ * <  √︀, *где  — некоторое число от 0 до  − 2 включительно,
 = Q( 1 , . . . ,  ),  заданы формулой (5.4). Тогда:
1. Числа
(︃
1 ,...,−1
√︀
√︀
= 1 ,...,−1 ( 1* , . . . , * ) =
(︃ (︃
×
−2
∏︁
)︃

˜  1−
(︃

−1  −1 +

∏︁
)︃

˜  1−
=1
−2
∏︁
×
)︃

˜ 1− 
)︃

˜ −1 (− )−1 ,
=+1
=+1
когда набор ( ) пробегает всевозможные наборы из {0, 1}−1 , образуют
фундаментальный базис поля  ∩ R.
12
2. Числа
(︃
*1 ,...,−1
(︃ (︃
× −
√︀
√︀
= *1 ,...,−1 ( 1* , . . . , * ) =
−2
∏︁
)︃

˜  1−
−1 (− )1−−1 +

∏︁
)︃

˜  1−
(︃=1−2
∏︁
=+1
×
)︃
)︃
1−−1

˜ 1− 

˜ −1 
,
=+1
когда набор ( ) пробегает всевозможные наборы из {0, 1}−1 , образуют
базис Z-модуля  ∩ R.
3. Для любых ,  ∈ {0, 1}−1 справедливо равенство
∑︁
(︀
)︀
(−1)1 +...+−1  1 ,...,−1 *1 ,...,−1 =
∈{0,1}−1
{︃
√︀
√︀
(−1)1 +...+−1 1* . . . * ,
=
0,
если  = ,
иначе.
*
Теорема 5.12. Пусть 1* , . . . , −1
нечётные положительные, * = −4 или
* = −8. Тогда:
1. Числа
1 ,...,−1 =
1 ,...,−1 (1* , . . . , * )
=
−1
∏︁

˜  1− ,
=1
когда набор ( ) пробегает всевозможные наборы из {0, 1}−1 , образуют
фундаментальный базис поля  ∩ R.
2. Числа
*1 ,...,−1 = *1 ,...,−1 (1* , . . . , * ) =
(︃ −1
∏︁
)︃

˜  1−
√︀
* ,
=1
когда набор ( ) пробегает всевозможные наборы из {0, 1}−1 , образуют
базис Z-модуля  ∩ R.
3. Для любых ,  ∈ {0, 1}−1 справедливо равенство
∑︁
(︀
)︀
(−1)1 +...+−1  1 ,...,−1 *1 ,...,−1 =
∈{0,1}−1
{︃
√︀
√︀
(−1)1 +...+−1 1* . . . * ,
=
0,
13
если  = ,
иначе.
В параграфе 5.5 предлагается новая модификация метода комплексного
умножения, заключающаяся в использовании вместо многочлена  [] его
ˆ  []. Напомним, что при определении (5.1) многочлена  [] по
делителя 
 определённым образом строится набор троек (, , ); их всегда можно
выбирать так, чтобы gcd(, ) = 1. Определим на них отображение  в
{±1} формулой
(︃ (︂ )︂
(︂ * )︂ )︃
*
1

(, , ) =
,..., 
,


(︀ )︀
где * , как и ранее, взяты из леммы 5.2, а  — символ Кронекера, мульти­
пликативный по , равный символу Лежандра при нечётных простых , для
 = 2 определённый только в случае  ≡ 0, 1 (mod 4) формулой
⎧
если  ≡ 1 (mod 8),
⎨1,
(︁  )︁ ⎪
= −1, если  ≡ 5 (mod 8),
⎪
2
⎩0,
если  ≡ 0 (mod 4).
Теорема
5.13. Образ отображения  совпадает с группой {(1 , . . . ,  ) :
∏︀
=1  = 1} с покомпонентным умножением. На наборе троек (, , )
из определения (5.1) можно ввести групповую структуру, относительно
которой  является гомоморфизмом групп.
ˆ  [] следующим образом:
Определим многочлен 
∏︁
ˆ  []() =

( − (, , )) .
(,,):(,,)=(1,...,1)
ˆ  [] легко вычислить по опреде­
Аналогично многочлену  [], многочлен 
лению с любой наперёд заданной точностью. В отличие от многочлена  [],
ˆ  [] имеет коэффициенты из  , поэтому для его использова­
многочлен 

ния в методе комплексного умножения нужно уметь восстанавливать числа
из  по достаточно точным приближениям.
В параграфе 5.6 вычислена оценка 0 на все сопряжённые к коэффици­
ˆ  []. Автоморфизмы из группы Галуа Gal( /Q) пере­
ентам многочлена 
ˆ  [] в многочлены вида
водят многочлен 
∏︁
ˆ
,0 []() =
( − (, , )) .
(,,):(,,)=0
14
ˆ , [] по модулю не
Теорема 5.14. Каждый коэффициент многочлена 
0
превосходит
{︂
(︂
)︂}︂
ln  +  + 1
2
exp 5 ℎ + 1  ln  + 4 ln  + 6 +

{︀
}︀
exp 1  ln2  + 2  ln  + 3  + 1 ln  + 4 ,
√︁
√
||
3 = 5.441...,
,

=
0.577...
—
константа
Эйлера,

=
где  =
1
3
2 = 18.587..., 3 = 17.442..., 4 = 11.594..., 5 = 3.011..., 6 = 2.566... Асимп­
тотическая верхняя оценка
(︁√︀
)︁
2
exp{
|| ln || }
также выполняется для других функций , подходящих для использования
в методе комплексного умножения.
В качестве 0 можно взять оценку из теоремы 5.14, но на практике предла­
гается использовать эвристическую, но более точную оценку
ln 0 ∼ 
√︀
|| max 
∈{±1}
∑︁
(,,):(,,)=
1

при использовании инварианта . При использовании других функций  сле­
deg Φ
дует умножить оценку на deg Φ , где Φ — многочлен от двух переменных,

связывающий  и , Φ((), ()) = 0 (такой многочлен существует для всех
, подходящих для использования в методе комплексного умножения).
Ещё одним необходимым этапом является построение совместных при­
ближений к элементам базиса  . Для построения совместных приближений
существуют различные универсальные алгоритмы, изучению которых посвя­
щена книга A. Brentjes1 . На практике характеристики получаемых прибли­
жений существенно различаются для разных алгоритмов, для практических
целей, по-видимому, наилучшим является алгоритм скалярных произведений
из главы 6A указанной книги. К сожалению, для универсальных алгорит­
мов довольно трудно получить теоретические оценки качества. Поэтому в
параграфе 5.7 мы предлагаем алгоритм, подходящий только для наборов чи­
сел нужного нам вида, работающий на практике примерно столь же хорошо,
сколь и алгоритм скалярных произведений. В том же параграфе мы доказы­
ваем для нашего алгоритма оценку качества получаемых приближений, по
порядку совпадающего с оценкой теоремы Дирихле.
1
Brentjes A. J. Multi-dimensional continued fraction algorithms. Amsterdam: Mathematisch Centrum,
1981.
15
Доказательство оценки качества основано на следующей теореме. Основ­
ную её часть по существу описал L. Peck2 , хотя в нашем случае утверждения
из этой работы неприменимы. Основные отличия нашей теоремы от работы
L. Peck заключаются в явной формулировке (в том числе явных константах),
введении функции M (L. Peck оперирует двойственными базисами, что экви­
валентно M = 1) и специализацией для интересующего нас случая (L. Peck
не требует нормальности расширения /Q и описывает также обратную тео­
рему).
Теорема 5.15. Пусть  ⊂ R — поле такое, что /Q — расширение
Галуа степени . Пусть 1 , . . . ,  и 1* , . . . , * — два Q-базиса  и
M : Gal(/Q) → R — функция (необязательно гомоморфизм) такие, что
для всех 1 , ′  выполнено равенство
{︃
∑︁
1, если  = ′ ,
*
M( ) ( ′ ) =
0, если  ̸= ′ .
 ∈Gal(/Q)
Обозначим
∑︁
=
|M( ) (1 )|
 ∈Gal(/Q)
 ̸=
и при  = 2, . . . , 
 =
∑︁
 ∈Gal(/Q)
 ̸=
⃒
(︂
)︂⃒
⃒
⃒

(
)
1
⃒M( )  ( ) − 
⃒.
⃒
⃒
1
Пусть также положительное число ∆ и целые числа Λ1 , . . . , Λ таковы,
что

∑︁
Λ * =  1,
=1
⃒ (︃ 
)︃⃒
⃒
⃒ ∑︁
⃒
* ⃒
Λ  ⃒
⃒
⃒
⃒
=1
∆
1
 −1
для всех  ∈ Gal(/Q),  ̸= .
Тогда:
∙ Справедливо неравенство |Λ1 |
|M()1 | − ∆.
∙ Если |Λ1 | > ∆, то M() ̸= 0 и при всех  = 2, . . . ,  справедлива
оценка
⃒
⃒
⃒ Λ
⃒
∆

⃒ −  ⃒ 
1 .
(︁
)︁ −1
⃒ Λ1 1 ⃒
|Λ1 |−Δ
|Λ1 | |M()
1|
2
Peck L. G. Simultaneous rational approximations to algebraic numbers // Bull. Amer. Math. Soc. 1961.
Vol. 67. Pp. 197–201.
16
Теорема применяется в случае  =  ∩ R,  = [ : Q] = 2−1 , к двум
наборам элементов  и * , нумеруемым векторами из {0, 1}−1 , образующим
базис  над Q и удовлетворяющим следующим условиям:
*
= 1.
1. 0,...,0
2. Любой элемент кольца целых  поля  разлагается по базису {* }
с целыми коэффициентами.
3. Если , ′ ∈ {0, 1}−1 , то
{︃
1,
M( ) ( *′ ) =
0,
∈{0,1}−1
если  = ′ ,
если  =
̸ ′ .
∑︁
(5.5)
Из теорем параграфа 5.4 следует, что базисы  и * после деления на пер­
вый элемент базиса удовлетворяют этим условиям. Более точно, выполнены
следующие утверждения.
Утверждение. Если
1 ,...,−1 =
* 1 ,...,−1 =
1 ,...,−1
0,...,0 ,
* ,...,
(−1)1 +...+−1 1 * −1 ,
0,...,0


*

,...,
1
−1 ( 0,...,0 0,...,0 )
 +...+
M(1 ,...,−1 ) = (−1)
1
−1
√
√
1* ...
*
(5.6)
,
то условия 1–3 выполнены.
Утверждение. Если
1 ,...,−1 =
* 1 ,...,−1 =
*1 ,...,−1
,
*
0,...,0
 ,...,
(−1)1 +...+−1 1 0,...,0−1 ,
*
1 ,...,−1 (0,...,0 0,...,0
)
 +...+
M(1 ,...,−1 ) = (−1)
1
−1
√
√
1* ...
*
(5.7)
,
то условия 1–3 выполнены.
Для описания алгоритма нам понадобятся следующие величины. Пусть
 ∈ {0, 1}−1 ,  ̸= (0, . . . , 0). Через ⊕ будем обозначать сложение целых чисел
по модулю 2. Положим
*
 = (1* )1 . . . (−1
)−1 (* )+1 ⊕...⊕−1 .
Если  чётно, положим
√
 =
в противном случае положим

,
2
√
1 + 
 =
.
2
17
Тогда  ∈  .
Поскольку {* } образуют Q-базис поля  и числа  лежат в этом поле,
то в самом начале можно предвычислить такие  ∈ Q, что
∑︁
*
  =
 * .

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

— целые числа  такие, что |0,...,0 | 0 и для каждого  ∈ {0, 1}−1 0,...,0

.
— приближение к 0,...,0
Алгоритм в процессе работы хранит набор из 2−1 целых чисел  , а так­
же вспомогательные наборы целых неотрицательных чисел  , натуральных
чисел ( , ˜ ) и вещественных положительных чисел ( , ˜ ), где  ∈ {0, 1}−1 ,
 ̸= (0, . . . , 0). Эти наборы имеют некоторый смысл, объяснённый в тексте
главы, в терминах цепных дробей к числам  .
Действия алгоритма.
1. Инициализация. Присвоить начальные значения: положить для всех
 ∈ {0, 1}−1 ,  ̸= (0, . . . , 0)
0,...,0


( , ˜ )
( , ˜ )
:=
:=
:=
:=
:=
1
0
0
(1, ⌊ 4 ⌋)
(1,  )
2. Итерации. Пока |0,...,0 | < 0 , повторять следующие шаги.
3. Выбрать некоторое  такое, что  = max̸=(0,...,0)  .
⌊︁
⌋︁
 +
4. Вычислить  =
.

5. Присвоить ( , ˜ ) := (˜
 −  ,  ).
{︀ }︀
6. Запомнить  =  , присвоить  :=  −  − 4 4 , после чего присво­
ить ( , ˜ ) := (˜
 − ( − ),  ). (При этом новое значение  всегда
целое неотрицательное, а новое значение  натуральное.)
7. Вычислить для всех 
∑︀
′ =

  +  
.
˜
(При этом ′ ∈ Z для всех .) Присвоить  := ′ .
18
Теорема 5.16. Алгоритм завершается за (ln 0 ) шагов. В процессе рабо­
ты алгоритма всегда выполнены неравенства
√︀
0  <  −  ,
√︀
0 <  <  ;
∑︁
 * 1,
=

⃒ (︃
)︃⃒
⃒
⃒
∑︁
⃒
* ⃒
  ⃒
⃒ 
⃒
⃒

√︀ 
||
1
 −1
при  ̸= (0, . . . , 0).
Из теорем 5.15 и 5.16 легко выводится следующее утверждение.
Следствие. Алгоритм даёт бесконечную последовательность приближений,
для которых верна оценка
⃒
⃒
⃒ 
⃒
1


⃒ ≪ |(0,...,0) |−1− 2−1 −1 .
max ⃒⃒
−

(0,...,0) (0,...,0) ⃒
Константа в знаке ≪ (которую можно выписать явно) зависит от  и от
выбора базиса * и функции M.
Параграф 5.8 завершает описание предлагаемой новой модификации ме­
тода, показывая, как с помощью совместных приближений, вычисленных в
параграфе 5.7, и знания оценки всех сопряжённых, вычисленной в параграфе
ˆ  [],
5.6, можно восстановить точные значения коэффициентов многочлена 
введённого в параграфе 5.5, в виде разложения по базису, найденному в па­
раграфе 5.4. В конце параграфа приводится общая схема предлагаемой мо­
дификации метода комплексного умножения.
Параграф 5.9, завершающий главу, содержит некоторые численные дан­
ные по сравнению скорости работы реализации исходного метода и нашей
модификации на отрезке 1000000 || < 1001000. Для случайных дискри­
минантов время уменьшилось примерно в два раза.
Результаты пятой главы опубликованы в работах [2] и [5].
Автор глубоко благодарен своим научным руководителям за постановку
задач и помощь в работе. Устинов Алексей Владимирович, доктор физико­
математических наук, привлёк моё внимание к изучению свойств операции
 →   , а также к работам Степанова и Коробова по оценкам числа то­
чек на гиперэллиптических кривых. Михаил Алексеевич Черепнёв, кандидат
физико-математических наук, доцент поставил задачу эффективного постро­
ения эллиптических кривых с предписанным порядком.
Автор испытывает огромную признательность всему коллективу кафед­
ры теории чисел и отделения аспирантуры механико-математического фа­
культета за поддержку в течение всего времени обучения в аспирантуре и
написания диссертации. Автор также благодарен коллегам по работе за про­
явленное понимание.
19
Работы автора по теме диссертации
1. Гречников Е. А. Двусторонние оценки числа неподвижных точек дискрет­
ного логарифма // Вестник Московского университета. Серия 1. Матема­
тика. Механика. 2012. № 3. С. 3–8.
2. Гречников Е. А. Метод комплексного умножения для построения эллипти­
ческих кривых и его оптимизации // Прикладная дискретная математика.
2011. Т. 13, № 3. С. 17–54.
3. Гречников Е. А. Оценка суммы символов Лежандра // Матем. заметки.
2010. Т. 88, № 6. С. 859–866.
4. Гречников Е. А. Суммы символов Лежандра от многочленов степени 5 //
Современные проблемы математики и механики, т.IV «Математика», вы­
пуск 3. Изд-во Московского университета. 2009. С. 136–145.
5. Гречников Е. А. Оптимизация метода с комплексным умножением постро­
ения эллиптической кривой. 2011. Деп. в ВИНИТИ 21.06.11, № 305-В2011.
20
Документ
Категория
Физико-математические науки
Просмотров
51
Размер файла
367 Кб
Теги
кандидатская
1/--страниц
Пожаловаться на содержимое документа