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

• Автор: Гречников, Евгений Александрович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Москва
• Количество страниц: 113 с. : ил.

Глава 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. Свойства изоморфизма П
5.4. Кольцо целых поля родов
5.5. Делитель многочлена Яр [в, а»] (х)
5.6. Оценка коэффициентов многочлена а:*]
5.7. Построение рациональных приближений к базису кольца целых
5.8. Вычисление элемента поля родов по приближённому значению
5.9. Время работы
Литература

Пусть р - - нечётное простое число. Настоящая диссертация посвящена рассмотрению следующих важных специальных уравнений:
Уравнение (1.1) можно рассматривать при различных дополнительных ограничениях на д и на х. Хронологически первым появился вопрос о существовании решений при каком-либо примитивном д он получил название проблемы Бризолиса (описана в книге [1] 1994 года). Если наложить дополнительное ограничение и рассматривать только примитивные корни х в качестве решений, то их число нетрудно асимптотически вычислить; это проделано в 1995 году в [2], независимо в 1999 году в [3] и даёт положительный ответ на проблему Бризолиса при всех достаточно больших р. Окончательно (то есть для всех р) проблема Бризолиса решена в 2003 году в [4] (а именно, такие решения существуют при всех р > 3). [4] не касается вопроса явного построения решений (1.1), конструкции при некоторых ограничениях на р рассматривает статья [5]. Кроме того, статья [5] улучшает оценку из [3] и доказывает также существование решений при некоторых д, не являющихся первообразными корнями. Хорошо известно [6], что к этой задаче может быть сведена задача универсальной подделки ГОСТ Р 34.10-94.
Очевидно, что число решений с примитивными д и х даёт нижнюю оценку числа решений при более слабых ограничениях. Гипотетические асимптотические равенства для чисел решений при различных наборах ограничений выдвинуты в 2002 году в [7]. В частности, усреднённое по всем (в том числе непримитивным) д число решений (1.1) без дополнительных ограничений на х гипотетически есть 1 + о(1) при р —> оо. Эта гипотеза оказалась трудной и в общем случае пока не доказана; в [8] (2006 год) она доказана для множества р положительной плотности (среди всех простых), в [9] (2008 год) — для множества р плотности 1. В ещё не опубликованной работе тех же авторов,
дх-=х (тобр), х Е {0,... ,р — 1} у2 = /(х) (тоб р), х,у & Fp,/е FpИ,2{бeg
(1.1)
(1.2)

что и [9], доказана верхняя оценка 0(1)
Усреднённое по примитивным д число решений (1.1) без дополнительных ограничений на х гипотетически есть также 1 + о(1) при р —» оо. В главе 2 мы докажем некоторые оценки для числа решений без ограничений на х в среднем по примитивным д; к сожалению, верхняя оценка оказывается слабее гипотетической. Этот результат содержится в нашей работе [51].
Если в уравнении (1.2) многочлен / делится на квадрат какого-либо многочлена, то это уравнение очевидной заменой переменных сводится к уравнению того же вида с многочленом меньшей степени. Далее будем считать, что / свободен от квадратов.
Если в уравнении (1.2) / — многочлен третьей степени (свободный от квадратов), то множество его решений вместе с одним «бесконечно удалённым» образует абелеву группу. Рассмотрение всех решений над Ер, а не только над приводит к эллиптической кривой. Теория эллиптических кривых исключительно обширна; её основы прекрасно изложены в книге [10], на которую мы будем часто ссылаться. В частности, неравенство Хассе (которое можно найти в [10]) задаёт ограничение на число решений уравнения (1.2) для любого возможного / степени 3 без кратных корней: это число решений (включая «бесконечно удалённое») не может отличаться от р+ 1 по модулю более чем на 2у/р. Теорема Дойринга-Ватерхауза ([11], [12]) применительно к полю Ер утверждает, что для любого числа в пределах оценки Хассе можно подобрать уравнение вида (1.2) с таким числом решений.
Формулировка теоремы Дойринга-Ватерхауза не задаёт уравнение вида (1.2) явным образом. Интересно также явное построение уравнения с предписанным числом решений или, по крайней мере, число решений которого будет удовлетворять предписанным условиям. Например, быть простым числом (с учётом «бесконечно удалённого» решения) или иметь большой простой делитель: работы [13] и [14] предлагают использование таких кривых в криптографии. Стойкость соответствующих криптографических схем опирается на сложность задачи дискретного логарифмирования в группе точек эллиптической кривой. В настоящий момент лишь в некоторых частных случаях известен эффективный алгоритм для решения этой задачи, и их легко

Наряду с классическим определением модулярного инварианта j как функции на верхней полуплоскости Н ([36, §46]) можно также определить j-инвариант решётки в С ([35, §10]), не меняющийся при умножении решётки на любое ненулевое комплексное число, так, что при т € И выполнено равенство j(r) = j((1,t)z). Если а — собственный дробный идеал Ор, то он является решёткой в С. При этом умножение идеала а на главный идеал приводит к умножению решётки на элемент из К* следовательно, значение j(a) зависит только от класса идеала а. С вычислительной точки зрения если дробный идеал а принадлежит классу, заданному формой Ат2 + Вху + Су2 с корнем т, то есть а ~ (1, r)z, то j(a) = j(r).
Для любой эллиптической кривой при п € Ъ определим отображение [га], переводящее точку Р в точку пР. В частности, [1] — тождественное отображение. Изогенией двух эллиптических кривых будем называть морфизм (в смысле алгебраической геометрии), переводящий бесконечно удалённую точку одной кривой в бесконечно удалённую точку другой, эндоморфизмом эллиптической кривой будем называть изогению в себя. При любом га € Z отображение [га] является эндоморфизмом эллиптической кривой ([10, Example III.4.1]) и коммутирует с любым другим эндоморфизмом (поскольку любая изогения эллиптических кривых является гомоморфизмом групп точек в силу [10, Theorem III.4.8]); кольцо эндоморфизмов эллиптической кривой является Z-модулем относительно действия пр — [га] о <р, где га е Z, р — эндоморфизм. Эндоморфизмы {[га] : п £ Z} образуют кольцо, изоморфное Z ([10, Proposition III.4.2]).
Кольцо эндоморфизмов эллиптической кривой над С либо совпадает с {[га] : га G Z}, либо изоморфно порядку в некотором мнимоквадратичном поле ([10, Corollary III.9.4 и Exercise 3.18b]). В последнем случае говорят, что кривая имеет комплексное умножение на этот порядок. Есть ровно Но неизоморфных эллиптических кривых с умножением на Оо ([10, Proposition С.11.1]), эти кривые характеризуются тем, что их j-инвариант совпадает со значением модулярного инварианта j(a), вычисленного на представителях классов идеалов О о- Эти значения называются сингулярными значениями. Любое такое значение генерирует над К одно и то же поле L = L{D) = K(j(a)), называемое полем классов кольца Op (ring class field)