Введение к работе
Актуальность темы
Одной из важных областей теории чисел является изучение конечных полей. Ещё Гаусс доказал, что в поле вычетов по любому простому модулю существует примитивный элемент д: для которого степени дх при различных целых х пробегают все ненулевые элементы поля. Степени дх можно легко вычислить, но для обратной задачи дискретного логарифмирования — нахождения х по значению дх — неизвестно эффективного алгоритма решения, на чём основаны некоторые криптографические схемы. Это привлекает внимание исследователей к изучению свойств возведения в степень в конечном поле. В частности, известно1, что задача универсальной подделки ГОСТ Г 34.10-94 может быть сведена к решению уравнения
дх = х (mod р), х Є {0,... ,р — 1}, (1)
где р — нечётное простое число. Это уравнение можно рассматривать при различных дополнительных ограничениях на д и на х. Хронологически изучение этого уравнения началось с вопроса о существовании решений при каком-либо примитивном д; этот вопрос получил название проблемы Бризолиса2. Если наложить дополнительное ограничение и рассматривать только примитивные корни х в качестве решений, то их количество асимптотически вычислено в 1995 году3, а также независимо в 1999 году4, что даёт положительный ответ на проблему Бризолиса при всех достаточно больших р. Окончательно (то есть для всех р) проблему Бризолиса решила М. Campbell5 в 2003 году (а именно, такие решения существуют при всехр > 3). М. Campbell не касается вопроса явного построения решений (1); М. А. Черепнёв6 строит конструкции при некоторых ограничениях на р: а также улучшает ранее известные оценки и доказывает существование решений при некоторых д: не являющихся первообразными корнями.
Очевидно, что число решений с примитивными д и х даёт нижнюю оценку числа решений при более слабых ограничениях. Гипотетические асимптотические равенства для чисел решений при различных наборах ограничений выдвинул J. Holden7 в 2002 году. В частности, усреднённое по всем (в том
1 Черепнёв М. А. Криптографические протоколы. Изд-во механико-математического факультета
МГУ, 2006.
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
числе непримитивным) д число решений (1) без дополнительных ограничений на х гипотетически есть 1 + о(1) при р —> оо. Эта гипотеза оказалась трудной и в общем случае пока не доказана; в 2006 году J. Holden и Р. Могее8 доказали гипотезу для множества р положительной плотности (среди всех простых). В 2008 году С. В. Конягин, И. Е. Шпарлинский и Ж. Бургейн9 доказали гипотезу для множества р плотности 1. В ещё не опубликованной работе тех же авторов доказана верхняя оценка O(l); работа доступна на как arXiv: 1103.0567. Усреднённое по примитивным д число решений (1) без дополнительных ограничений на х гипотетически есть также 1 +о(1) при р —> оо.
Другим важным объектом в теории конечных полей являются уравнения от двух переменных, задаваемые многочленами. Здесь теория чисел тесно связана с алгебраической геометрией.
Более конкретно, рассмотрим уравнение
y2 = f(x) (modp), x,yep,fep[x],2\degf. (2)
Если многочлен / делится на квадрат какого-либо многочлена, то это уравнение очевидной заменой переменных сводится к уравнению того же вида с многочленом меньшей степени. Далее будем считать, что / свободен от квадратов.
Если / — многочлен третьей степени (свободный от квадратов), то множество решений уравнения (2) вместе с одним «бесконечно удалённым» образует абелеву группу. Рассмотрение всех решений над р: а не только над р: приводит к эллиптической кривой. Теория эллиптических кривых исключительно обширна; её основы прекрасно изложены в книге J. Silverman10. В частности, неравенство Хассе устанавливает двустороннюю оценку на число решений уравнения (2) для любого возможного / степени 3 без кратных корней: это число решений (включая «бесконечно удалённое») не может отличаться от р+ 1 по модулю более чем на 2^/р. Теорема Дойринга-Ватерхауза11'12 применительно к полю р утверждает, что для любого числа в пределах оценки Хассе существует уравнение вида (2) с таким числом решений.
Операция сложения в группе точек эллиптической кривой легко вычислима. Следовательно, операция умножения точки Р на целое число Р ь-> пР: п Є Z, также эффективно вычислима. Однако для обратной операции дискретного логарифмирования на эллиптической кривой — вычисления п по
8 Holden J., Могее 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 Funktionenkorper // 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.
известным точкам Р и пР — в общем случае неизвестно эффективного алгоритма, на чём основаны некоторые криптографические схемы13'14. Для этих схем важно, чтобы порядок группы точек был простым числом или, по крайней мере, имел большой простой делитель. Кроме того, в некоторых специальных случаях дискретное логарифмирование всё же возможно15'16; их легко запретить дополнительными условиями на порядок группы точек.
Теорема Дойринга-Ватерхауза гарантирует существование эллиптической кривой с нужным порядком, но не содержит способа построения такой кривой. Один из возможных методов построения — случайно выбирать коэффициенты уравнения кривой и подсчитывать число точек с помощью алгоритма Шуфа в цикле, пока вычисленное число точек не удовлетворяет заданным условиям. Следует отметить, что вероятность случайно получить кривую с порядком, делящимся на большое простое число, не слишком велика. Кроме того, сложность алгоритма Шуфа хотя и полиномиальна (по размеру входных данных), но растёт достаточно быстро.
Другой, более эффективный способ построения эллиптических кривых — метод комплексного умножения. Для простых полей первый её вариант описали A. Atkin и F. Morain17 в 1993 году (в качестве вспомогательного средства для алгоритма проверки простоты), для произвольных конечных полей, включая поля характеристики 2, — G.-J. Lay и Н. Zimmer18 в 1994 году. В дальнейшем этот метод неоднократно улучшали19'20'21'22.
Если в уравнении (2) / — многочлен нечётной степени п > 3 (свободный от квадратов), то множество решений этого уравнения над р вместе с одним «бесконечно удалённым» есть гиперэллиптическая кривая рода z?yk Представим число Fp-точек кривой в виде р + 1 + N: или, что эквивалентно, число решений уравнения (2) в виде р + N. Оценка Вейля, доказанная средствами
13 Koblitz N. Elliptic curve cryptosystems // Mathematics of Computation. 1987. Vol. 48. Pp. 203-209.
14 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 p-torsion points of an elliptic curve in
characteristics p // 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
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 Theorie 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.
алгебраической геометрии, утверждает, что \N\ ^ (п — 1)у/р. В 1969 году С. А. Степанов23 доказал элементарными методами оценку \N\ ^ л/Зпп-^/р при р > 9п2. Доказательство основывается на построении ненулевого многочлена не слишком большой степени такого, что все числа х : ( ^-^-) = 1 являются его корнями достаточно высокой кратности, откуда следует оценка на их количество. Степанов строил такой многочлен как линейную комбинацию с неопределёнными коэффициентами. Позднее, в 1971 году Н. М. Коробов24 построил аналогичный многочлен явным образом, что позволило получить
элементарным методом оценку \N\ ^ (п — 1)л/р — п~ ^n~ . В 2005 году
Д. А. Митькин25 выдвинул утверждение \N\ ^ (п — 1)\/_р — 4 —-, но его доказательство неполное, так как использует лемму из статьи Коробова для значений параметров, не подходящих под ограничения из статьи Коробова.
Цель работы
Цель диссертации — получение новых оценок на количество решений уравнений
дх = х (mod р), х Є {0,... ,р — 1}, (3)
y2 = f(x) (modp), x,yep,fep[x],2\degf, (4)
где р — простое нечётное, а также оптимизация построения эллиптических кривых, для которых соответствующее уравнение вида (4) имеет число решений с предписанными свойствами.
Научная новизна
Результаты диссертации являются новыми и состоят в следующем:
Получены двусторонние оценки на число решений уравнения (3) в парах (д,х), где д — первообразный корень по модулю р. В частности, доказано, что в случае, когда имеется растущая последовательность простых р, для которых р— 1 не имеет простых делителей в отрезке [ "nki" ' Pl^s] для фиксированного натурального s, то среднее число решений по всем первообразным д есть 1 + о(1).
Доказано, что число решений уравнения (4) в парах (ж, у) при deg/ = 2д + 1 отличается от р по модулю менее чем на 1дур + 1 — д2-
23 Степанов С. А. О числе точек гиперэллиптической кривой над простым конечным полем //
Известия АН СССР. Серия математическая. 1969. Т. 33, № 5. С. 1171-1181.
24 Коробов Н. М. Оценка сумм символов Лежандра // Доклады АН СССР. 1971. Т. 196, № 4. С.
764-767.
25 Митькин Д. А. Уточнение оценки для суммы символов Лежандра от многочленов нечётной сте
пени // Чебышевский сборник. 2005. Т. 6, № 3. С. 123-126.
Получена оценка снизу на максимальное число решений уравнения (4) при deg / = 5. В частности, показано, что для любого р эта оценка отличается от полученной верхней оценки не более чем на 3. Доказательство содержит конструктивное построение гиперэллиптических кривых рода 2 большого порядка (соответствующих уравнению вида (4) с deg / = 5) из эллиптических кривых.
Предложена новая модификация метода построения эллиптических кривых, использующего комплексное умножение. Показано, что можно эффективно использовать делитель многочлена Гильберта с коэффициентами, являющимися целыми в поле родов мнимоквадратичного поля.
Вычислен базис кольца целых поля родов мнимоквадратичного поля. Предложен алгоритм построения совместных рациональных приближений к элементам построенного базиса. Доказаны оценки на скорость сходимости типа Дирихле.
Предложен алгоритм восстановления точных значений коэффициентов разложения целого алгебраического числа из поля родов мнимоквадратичного поля по приближённому значению числа и оценке модуля всех сопряжённых к нему.
Написана программа, которая строит эллиптические кривые с числом точек, равным простому числу вида Софи Жермен.
Основные методы исследования
В диссертации используются методы из алгебраической и алгоритмической теории чисел.
Теоретическая и практическая ценность
В диссертации доказываются теоремы и выводятся формулы, которые могут найти применение в алгебраической теории чисел. Построенные алгоритмы с оценками сложности могут использоваться в вычислительной теории чисел. Программа для построения эллиптических кривых на основе результатов главы 5 диссертации внедрена в НИИ «Автоматики».
Апробация работы
Результаты диссертации докладывались автором на следующих научных семинарах и конференциях:
на научно-исследовательском семинаре кафедры теории чисел (МГУ,
Москва, 2011 г.);
на семинаре «Теоретико-числовые вопросы криптографии» (МГУ, Москва, неоднократно 2008-2010 гг.);
на конференции «Ломоносовские чтения» (МГУ, Москва, 2009 г.);
на X международной конференции «Интеллектуальные системы и компьютерные науки» (МГУ, Москва, 2011 г.).
Публикации
Гезультаты автора по теме диссертации опубликованы в 5 работах [1], И, [3], [4], [5].
Структура и объём диссертации
Диссертация состоит из введения, четырёх глав и библиографии (54 наименований). Общий объём диссертации составляет 113 страниц.
