Введение к работе
Актуальность темы.
Последние десятилетия научных исследований в области алгоритмической теории чисел показали большую востребованность математического аппарата эллиптических кривых в решении сложных теоретико-числовых задач. Среди таких задач стоит отметить задачу разложения больших целых чисел на множители или задачу доказательства простоты больших натуральных чисел. Эллиптические кривые востребованы в различных прикладных областях математики, к которым можно отнести криптографию и теорию кодирования информации.
Хорошо известно, что эллиптические кривые могут быть заданы при помощи нескольких различных способов, например, в виде плоской кривой в форме Вейерштрасса или пересечения двух поверхностей в трехмерном пространстве. Каждый из способов позволяет исследовать новые свойства, которые могут быть использованы для решения поставленных задач.
В диссертационной работе рассматриваются эллиптические кривые, задаваемые системами уравнений второй степени. Этот способ тесно связан с соотношениями, которым удовлетворяют тэта-функции К-Якоби1 и представляется недостаточно хорошо изученным, с точки зрения его приложений к алгоритмическим вопросам теории чисел.
Основное внимание в диссертационной работе уделено трем вопросам: вычислению целочисленных решений системы связанных уравнений Пелля, задаче определения порядка группы точек эллиптической кривой, заданной системой уравнений уравнений второй степени и разработке метода разложения больших целых чисел на множители с использованием эллиптических кривых, заданных системами уравнений.
Впервые метод решения систем связанных уравнений Пелля был предложен в 1969 году в публикации А.Бейкера и Г. Дэвенпорта2. Далее метод развивался в работах Г. Гринстида3, Р. Пинча4 и В. Англина5.
Нами предложена модификация данного метода, использующая оценку Е.М. Матвеева6 для формы от трех логарифмов алгебраических чисел и позволившая разработать эффективный алгоритм поиска решений. Данный алгоритм был реализован нами на ЭВМ и позволил получить в явном виде решения ряда систем.
Вопрос о вычислении порядка группы точек кривой, заданной в короткой форме Вейерштрасса считается решенным. Алгоритм вычисления порядка группы
1Мамфорд Д. Лекции о тэта-функциях. — Н.:НФМИ, 1998. — 440 с.
1 Baker A., Davenport Я. The Equations Зі* - 2 = у* and 81а - 7 = г' // The Quaterty Journal of Mathematics, Oxford. - 1969. - V.20, №78.
3 Grinstead CM. On a Method of Solving a Class of Diophantine Equations // Math. Сотр. - 1978. — V.32. -p. 936-940.
* Pinch R.G.E. Simultaneous Pell Equations// Math.Proc. Cambridge Phitos. Soc. — V.103. — 1988. — p.35-46.
"Mnolm W.S. Simultaneous Pell Equations // Math. Сотр. - 1996. - V.65, № 213. - p.355-359.
6Матвеев E.M. Явная нижняя оценка однородной рациональной линейной формы от логарифмов алгебраиЛ ческих чисел. П // Матем. сб. — 2000. — том.64, №6. — стр.125-180.
был предложен в 1985 году Р. Шуфом7 8 и, позднее, модифицирован А. Аткиным и Н. Элкисом9.
Нами приводятся доказательства теорем, из которых следует, что вопрос об определении порядка группы точек эллиптической кривой, заданной системой уравнений второй степени, может быть сведен к определению порядка некоторой кривой, заданной в короткой форме Вейерштрасса.
Мы приводим три различных подхода к доказательству данного результата. Первый подход основан на методе, предложенным Дойрингом для вычисления порядка эллиптической кривой в форме Вейрштрасса. Второй — на представлении порядка эллиптической кривой, заданной системой уравнений, в виде сумм символов Лежандра, взятых отдельно по квадратичным вычетам и квадратичным невычетам по модулю простого числа. Третий подход основан на построении явного отображения точек одной кривой в точки другой.
В третьей главе диссертации мы рассматриваем задачу разложения больших целых чисел на множители. В 1985 году X. Ленстра10 предложил алгоритм факторизации, использующий вычисления с эллиптическими кривыми. Поскольку оценка трудоемкости данного алгоритма зависит от величины наименьшего делителя раскладываемого на множители числа, алгоритм X. Ленстры используется используется в качестве составной части в других алгоритмах, например, в алгоритмах квадратичного решета1112 или решета числового поля1314. Позднее алгоритм Ленстры был модифицирован в статьях П. Монтгомери15, Р. Брента16, а также работе братьев Чудновских17.
Нами описывается оригинальный алгоритм факторизации, использующий вычисления с эллиптическоми кривыми, задаваемыми системами уравнений, развивающий идеи Х.Ленстры и Р.Брента. Получена асимптотическая оценка трудоемкости изложенного алгоритма и приведены точные значения параметров алгоритма, позволяющие снизить оценку трудоемкости при некоторых ограничениях на размер факторизуемого числа.
1Schoof R. Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p // Math. Сотр. — V.44. - 1985. - p.483-494.
sSchoof R. Counting Points On Elliptic Curves Over Finite Fields // J. Theorie des Nombres de Bordeaux. — Vol. 7. - 1995. - p.219-254.
aDewaghe I. Remarks on the Schoof-Elkies-Atldn algorithm. - Math. Сотр. — V.67. -1998. - p.1247-1252.
"towrra B. W. Factoring Integers with Elliptic Curves // Ann. Math. - 1987. — № 126. — p.649-673.
nPomerance C. The Quadratic Sieve Factoring Algorithm // EUROCRYPT-84. - Lecture Notes in Computer Science, 209. - Sprioger-Veilag. — 1985. - pp.169-182.
"Silverman R. The Multiple Polynomial Quadratic Sieve // Math. Of Сотр. — V.48. — 1987. - p.329-339.
13Letutra A.K. and lenstra ff. W., Jr.. The Development of The Number Field Sieve. — Lecture Notes in Math, 1554. - Springer -1993.
uPomerance С A Tale of Two Sieves// Notices of the AMS. - V.43. - 1996. p.1473-1485.
15 Montgomery P.L. Speeding The Pollard and Elliptic Curve Methods of Factorization // Math, of Сотр. — 1987. - Vol. 48. - № 177. - P. 243-267.
leBrent R.P. Some Integer Factorization Algorithms Using Elliptic Curves // Australian Computer Science Communacations. — 1986. — № 8. — p. 149-163.
17 Chudnovsky D., Chudnovsky G. Sequences of Numbers Generated by Addition in Formal Groups and New Ptimality and Factorization tests // Advances in Applied Mathematics. — 1987. — № 7. — p. 385-434.
a.
Научная новизна работы.
Основные результаты, полученные в диссертации, являются новыми и состоят в следующем.
Разработан оригинальный алгоритм нахождения целочисленных решений систем связанных уравнений Пелля.
Доказано равенство порядков групп точек эллиптической кривой, заданной системой уравнений, и эллиптических кривых, заданных в форме Якоби и Вейерштрасса.
Разработан новый вариант алгоритма Ленстры разложения больших целых чисел на множители, использующий вычисления с эллиптическими кривыми, задаваемыми системами уравнений.
Все разработанные автором диссертации алгоритмы реализованы им лично на ЭВМ, что позволило в явном виде получить решения поставленных задач.
Методы исследования.
В диссертации используются методы теории оценок линейных форм от логарифмов алгебраических чисел, теория непрерывных дробей, методы оценок сумм квадратиченых вычетов, методы теории сложности, а также результаты о числе гладких чисел в заданном интервале.
Теоретическая и практическая ценность.
Диссертация носит теоретический и прикладной характер. Ее результаты могут имеют приложения в дифференциальной геометрии, а также в некоторых областях теории кодирования и криптографии.
Аппробация работы.
Результаты диссертации докладывались автором на научном семинаре механико-математического факультета МГУ им.М.В. Ломоносова, а также на следующих научных конференциях конференциях:
IV Международной конференции «Современные проблемы теории чисел и ее приложения» (Тула, 2001 г.)
Конференции «Математика и безопасность информационных технологий» в МГУ им. М.В. Ломоносова (Москва, 2003 г. и 2004 г.)
VII международной научно-технической конференции «Новые информационные технологии и системы» (Пенза, 2006 г.)
III международной конференции по проблемам безопасности и противодействия терроризму в МГУ им. М.В. Ломоносова (Москва, 2007 г)
Публикации.
Результаты диссертации опубликованы в 8 работах, список которых приводится в конце автореферата.
Структура диссертации.
Диссертация состоит из введения, трех глав, заключения, библиографического списка, включающеего 44 наименования, и приложения, в котором приведены точные решения ряда систем связанных уравнений Пелля. Общий объем диссертации 65 страниц.
