Алгоритмические приложения эллиптических кривых, задаваемых системами уравнений

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

Оглавление
Введение
1 Нахождение целочисленных решений системы связанных уравнений Пелля
1.1 Представление квадратичными формами
1.2 Оценки числа решений
1.2.1 Определение максимального индекса
1.2.2 Верхняя оценка линейной формы
1.2.3 Нижняя оценка линейной формы
1.3 Уменьшение верхней оценки
2 О числе решений одной системы сравнений
2.1 Первое доказательство теоремы 2.1
2.2 Второе доказательство теоремы 2.1
2.3 Доказательство второй теоремы
2.4 Примеры вычислений
2.5 Дополнение: построение изогений
3 Об одном варианте метода Ленстры факторизации целых чисел
3.1 Определение кривой над кольцом вычетов
3.2 Алгоритм факторизации
3.3 Алгоритм построения кривой
3.4 Об оценке трудоемкости алгоритма
3.4.1 Верхняя оценка трудоемкости алгоритма
3.4.2 Асимптотическая оценка трудоемкости
3.5 Результаты вычислений
Заключение
Литература
А Список решений ряда систем связанных уравнений Пелля

Введение
Во многих областях математики возникают задачи связанные с поиском решений и исследованием свойств нелинейных систем уравнений. В настоящей диссертационной работе изучаются системы уравнений второй степени от трех неизвестных, коэффициенты которых удовлетворяют некоторым ограничениям и могут принадлежать либо кольцу целых чисел, кольцу вычетов по модулю некоторого целого числа, либо конечному полю, характеристики отличной от двух.
В диссертационной работе мы рассматриваем несколько независимых математических задач, которые возникают в связи с изучением подобных систем уравнений.
В первой главе мы описываем алгоритм поиска всех целочисленных решений систем связанных уравнений Пелля
Г х2 — (2к + 1)г2
у2-(21 + 1)г2 = 12 (1)
где параметры 1,к- различные натуральные числа. Поиск решений систем диофантовых уравнений вида (1) интересен не только сам по себе, но и востребован в некоторых задачах дифференциальной геометрии [16].
Впервые метод решения систем диофантовых уравнений подобного вида был предложен в 1969 году в публикации А.Бейкера и Г. Дэвенпорта [21]. Далее метод развивался в работах Г. Гринстида [27], Р. Пинча [36] и В. Англина [19]. Указанными авторами предлагалось вычислять несколько независимых бесконечных серий решений для каждого из уравнений системы (1) и, рассматривая пересечения, получать оценку сверху для числа возможных решений. Для вывода оценки используется теория линейных форм от логарифмов алгебраических чисел.
Автором предложена модификация данного метода. Используя оценку Е.М.Матвеева [9] для формы от трех логарифмов алгебраических чисел, мы получаем более точные оценки сверху для числа решений системы (1). Более того, предложена итерационная процедура, использующая вычисления с подходящими дробями иррациональных чисел и позволяющая уменьшить полученную ранее оценку.
Предложенный метод был реализован автором на ЭВМ и решены системы вида (1) для всех значений параметров, удовлетворяющих неравенству 1 к < I 100. Результаты первой главы докладывались автором
в 2001 году на IV международной конференции «Современные проблемы
теории чисел и ее приложения» [10], научном семинаре кафедры теории чисел механико-математического факультета МГУ. им. М.В.Лоносова в 2002 году и были полностью опубликованы в 2009 году в статье [13].
Вторая глава диссертационной работы посвящена исследованию систем сравнений вида
Г и + и = 1 (mod р),
У и + и = 1 (mod р), где параметр А удовлетворяет условию А ф 0,1 (mod р) и р > 2 — простое число.
Хорошо известно, см., например, [8, гл. I] или исторический обзор в книге [18], что множество решений данной системы сравнений является эллиптической кривой, то есть абелевой группой. Используя терминологию, принятую в алгебраичекой геометрии, мы будем называть решения системы (2) точками кривой.
В случае, если система (2) рассматривается над полем комплексных чисел, то ее решения могут быть параметризованы эллиптическими функциями К. Якоби [4]. Соотношения, которым удовлетворяют эллиптические функции К. Якоби, позволяют определить на множестве решений системы (2) операцию сложения. Данные соотношения могут быть эффективно реализованы на ЭВМ, что было показано в работах [23, 33]. В 2004 году автором были предложены, см. [11], более эффективные соотношения для определения операции сложения решений рассматриваемых систем сравнений, основанные на свойствах тета-функций К. Якоби.

Приведем несколько примеров и для начала рассмотрим эллиптическую кривую Ео, заданную сравнением
у2 = х{х — ){х — 840356) (mod 1746821).
Порядок данной кривой равен 1745012 = 4 436253 и, согласно утверждению первой теоремы, совпадает с порядком группы, определяемой системой сравнений
( и + и2 = 1 (mod 1746821),
840356«! + «1 = 1 (mod 1746821),
Приведем второй пример и рассмотрим эллиптическую кривую, заданную в короткой форме Вейерштрасса сравнением
Е2 : у2 -Зх + 746011 (mod 1392707).
Нам известно, что порядок данной кривой равен 1391816 = 8 173977. Для построения системы сравнений вида (2.1) вычислим инвариант эллиптической кривой Е2
1728 4 = 4- (746011)2= 1183535 (mod 1392707)
и рассмотрим равенство (2.18) из которого следует, что параметр Л является корнем многочлена шестой степени
1183535 (Л2(Л - I)2) - 28 (А2 - А + l)3 = 0 (mod 1392707).
Корнем данного многочлена является значение А = 79115. Остальные корни этого многочлена, см. [7, гл. 18, §6], удовлетворяют сравнениям
-4— = 242774 (mod 1392707),

- 245077 (mod 1392707), = 1147631 (mod 1392707),

-4— = 1149934 (mod 1392707), 1 - А = 1313593 (mod 1392707).

Таким образом, эллиптической кривой Е2 соответствует шесть систем сравнений (2.1)
S, Si-, Si, Si, Sx=i, Si,
A A—1 A 1 A