Алгоритмические приложения эллиптических кривых, задаваемых системами уравнений тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат физико-математических наук Нестеренко, Алексей Юрьевич

• Нестеренко, Алексей Юрьевич
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Нестеренко, Алексей Юрьевич

Введение

1 Нахождение целочисленных решений системы связанных уравнений Пелля

1.1 Представление квадратичными формами.

1.2 Оценки числа решений.

1.2.1 Определение максимального индекса.

1.2.2 Верхняя оценка линейной формы.

1.2.3 Нижняя оценка линейной формы.

1.3 Уменьшение верхней оценки

2 О числе решений одной системы сравнений

2.1 Первое доказательство теоремы 2.

2.2 Второе доказательство теоремы 2.

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 у2 - (21 + 1)г2 = I2 (1) где параметры к - различные натуральные числа. Поиск решений систем диофантовых уравнений вида (1) интересен не только сам по себе, но и востребован в некоторых задачах дифференциальной геометрии [16].

Впервые метод решения систем диофантовых уравнений подобного вида был предложен в 1969 году в публикации А.Бейкера и Г. Дэвенпор-та [21]. Далее метод развивался в работах Г. Гринстида [27], Р. Пинча [36] и В. Англина [19]. Указанными авторами предлагалось вычислять несколько независимых бесконечных серий решений для каждого из уравнений системы (1) и, рассматривая пересечения, получать оценку сверху для числа возможных решений. Для вывода оценки используется теория линейных форм от логарифмов алгебраических чисел.

Автором предложена модификация данного метода. Используя оценку Е.М.Матвеева [9] для формы от трех логарифмов алгебраических чисел, мы получаем более точные оценки сверху для числа решений системы (1). Более того, предложена итерационная процедура, использующая вычисления с подходящими дробями иррациональных чисел и позволяющая уменьшить полученную ранее оценку.

Предложенный метод был реализован автором на ЭВМ и решены системы вида (1) для всех значений параметров, удовлетворяющих неравенству 1 ^ А: < / ^ 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 году автором были предложены, см. [II], более эффективные соотношения для определения операции сложения решений рассматриваемых систем сравнений, основанные на свойствах тета-функций К. Якоби.

Основным предметом исследований, отраженных во второй главе диссертационной работы, является вопрос о вычислении порядка группы точек кривой, заданной системой сравнений (2), для заданного значения параметра Л. Для эллиптических кривых, заданных в короткой форме Вейерштрас-са, этот вопрос является решенным. Алгоритм вычисления порядка группы был предложен в 1985 году Р. Шуфом [И, 12] и, позднее, модифицирован А. Аткиным и Н. Элкисом [29].

Во второй главе диссертационной работы автором доказываются теоремы 2.1 и 2.2, из которых следует, что для любой системы сравнений (2) найдутся эллиптические кривые

Е\ \ у2 = х(х - 1)(х - X) (то¿р), (3) у~ =ж3-^(1 + 14Л + А2)я-|-(1-ЗЗА-ЗЗА2 + А-!) (тех! р), (4) о с таким же порядком группы точек. Этот результат позволяет сводить задачу вычисления порядка группы точек кривой (2) к определению порядка одной из перечисленных кривых.

Мы приводим три различных подхода к доказательству существования эллиптической кривой с таким же порядком группы точек. Первый подход основан на методе, предложенным Дойрингом для вычисления порядка эллиптической кривой Е\. Второй — на представлении порядка эллиптической кривой Е\ в виде сумм символов Лежандра, взятых отдельно по квадратичным вычетам и квадратичным невычетам по модулю простого числа р. Оба подхода используются для доказательства теоремы 2.1.

Для доказательства теоремы 2.2 мы используем третий подход — в явном виде строим отображение множества решений системы (2) на множество точек эллиптической кривой Результаты второй главы полностью опубликованы в 2009 году работе [14].

В третьей главе диссертации мы рассматриваем задачу разложения больших целых чисел на множители. В 1985 году [31] X. Ленстра предложил алгоритм поиска делителей целого числа, использующий вычисления с эллиптическими кривыми. Поскольку оценка трудоемкости данного алгоритма зависит от величины наименьшего делителя раскладываемого на множители числа, алгоритм X. Ленстры, обычно, используется используется в качестве составной части в других алгоритмах, например, в алгоритмах квадратичного решета [38, 43] или решета числового поля [32, 39].

В первоначальном варианте алгоритма X. Ленстры предлагалось использовать для факторизации эллиптические кривые, заданные в аффинной форме записи. Позднее, П. Монтгомери [31] предложил использовать проективные координаты эллиптической кривой, а Р. Брент [21] — дополнить алгоритм вторым этапом, увеличивающем вероятность успешного завершения алгоритма. В работе братьев Чудновских [20] было замечено, что для реализации алгоритма можно использовать проективные абелевы многообразия, однако до последнего времени не было известно многообразий, допускающих эффективную реализацию группового закона.

В работе [11] автором была рассмотрена система уравнений, множество решений которой образует абелеву группу. Позднее автор показал, что множество решений рассмотренной системы уравнений может быть сведено к множеству решений хорошо известной системы уравнений аффинная форма которой рассматривалась нами во второй главе настоящей работы. Если решения системы (5) принадлежат некоторому полю, характеристики отличной от двух, то множество решений является эллиптической кривой и образует абелеву группу относительно операции сложения [4, 23, 33].

В третьей главе автором описывается разработанный им алгоритм разложения на множители нечетного, натурального числа N, основаный на идеях Х.Ленстры и Р.Брента и использующий вычисления со множеством решений системы (5) в кольце вычетов Ъм

Автором получена асимптотическая оценка трудоемкости изложенного алгоритма и приведены результаты реализации данного алгоритма на ЭВМ. Приведены точные значения параметров алгоритма, позволяющие снизить оценку трудоемкости при некоторых ограничениях на размер фак-торизуемого числа N.

5)

Результаты третьей главы докладывались на конференции «Математика и безопасность информационных технологий» в 2003 и 2007 годах и опубликованы в работах [11, 12].

Основные результаты, выносимые на защиту. Автором выносятся на защиту следующие основные результаты:

• Алгоритм нахождения целочисленных решений системы (1) связанных уравнений Пел ля.

• Доказательство равенства порядка групп точек эллиптической кривой, заданной системой сравнений (2) и эллиптических кривых, заданных в форме Вейерштрасса соотношениями (3) и (4).

• Новый вариант алгоритма Ленстры разложения больших целых чисел на множители, использующий вычисления с решениями системы уравнений (5) в кольце вычетов Ъ^.

Все выносимые на защиту результаты являются новыми и получены автором самостоятельно. По теме диссертации автором опубликовано 5 научных работ [10, 11, 12, 13, 14].

Диссертация состоит из введения, трех глав, списка литературы и приложения, в котором приведены решения систем связанных уравнений Пел-ля для некоторых значений параметров. Общий объем диссертации составляет 65 страниц.

Заключение диссертации по теме «Математическая логика, алгебра и теория чисел», Нестеренко, Алексей Юрьевич

Заключение

В диссертационной работе рассмотрены задачи, возникающие в связи с исследованием эллиптических кривых, задаваемых системами уравнений второй степени.

В первой главе разработан оригинальный алгоритм нахождения целочисленных решений систем связанных уравнений Пелля. Данный алгоритм математически обоснован и реализован на ЭВМ. Результаты экспериментов приведены в приложении к диссертационной работе.

Во второй главе рассмотрен вопрос о вычислении порядка группы точек эллиптической кривой, задаваемой в форме системы сравнений. Доказан результат о равенстве порядка группы точек рассматриваемой кривой и кривой, заданной в короткой форме Вейерштрасса. При доказательстве использованы два различных подхода, позволяющих в явном виде предъявить отображение множества точек одной кривой во множество точек другой.

В третьей главе предложен новый алгоритм факторизации — разложения больших целых чисел на множители. Алгоритм математически обоснован, получена асимптотическая оценка сложности алгоритма и показано, что она зависит от размера минимального делителя факторизуемого числа. Вычислены точные значения параметров алгоритма, позволяющие минимизировать трудоемкость алгоритма при известных ограничениях на размер мииимального простого делителя раскладываемого на множители числа.

Список литературы диссертационного исследования кандидат физико-математических наук Нестеренко, Алексей Юрьевич, 2009 год

1. Боревич З.И., Шафаревич И.Р. Терпя чисел. — 3-е изд. — М.:Наука, 1985. — 503 с.

2. Венков Б.А. Элементарная теория чисел. Математика в монографиях. Серия обзоров, вып.4. - М.-.ОНТИ НКТП СССР, 1937.

3. Гелъфонд А.О., Линник Ю.В. Элементарные методы в теории чисел.- М.:Физматгиз, 1962. — 272 с.

4. Гурвиц А. Теория аналитических и эллиптических функций. — М.:ГТТИ, 1933. 344 с.

5. Касс&ас Дж. Диофантовы уравнения со специальным рассмотрением эллиптических кривых // Математика, сб. переводов — 1968. — т. 12, вып.2 — стр. 3-48.

6. Кнут Д. Искусство программирования для ЭВМ. Получисленные алгоритмы. — М.:Мир. — 1977.

7. Лет С. Эллиптические функции. — М.:Наука, 1984. — 312 с.

8. Мамфорд Д. Лекции о тэта-функциях. — Н.:НФМИ, 1998. — 440 с.

9. Матвеев Е.М. Явная нижняя оценка однородной рациональной линейной формы от логарифмов алгебраических чисел. II // Матем. сб.2000. — том.64, №6. — стр. 125-180.

10. Нестеренко А.Ю. О нахождении целочисленных решений системы связанных уравнений Пел ля //IV Межд. конф. «Современные проблемы теории чисел и ее приложения», тезисы докладов. — Тула, 2001. 88стр.

11. Нестеренко А.Ю. О групповых свойствах одной системы уравнений // Материалы конференции «Математика и безопасность информационных технологий» в МГУ 23-24 октября 2003 г. — М.:МЦНМО — 2004. стр. 221-222.

12. Нестеренко А.Ю. Об одном варианте метода Ленстры факторизации целых чисел // Материалы третьей международной конференции по проблемам безопасности и противодействия терроризму в МГУ 25-27 октября 2007 г. М.:МЦМНО, 2008. - стр. 234-240.

13. Нестеренко А.Ю. Нахождение целочисленных решений системы связанных уравнений Пелля // Математические заметки. — 2009. — Том 86, вып. 4. — стр.588-600.

14. Нестеренко А.Ю. О числе решений одной системы сравнений // Депонировано во ВИНИТИ. № 454-в2009. - 2009. - 17 стр.

15. Прахар К. Распределение простых чисел. — М.:Мир. — 1967. — 511 с.

16. Сабитов И.Х. Исследование жесткости и неизгибаемости аналитических поверхностей вращения с уплощением в полюсе // Вестник МГУ, 1986. № 5. - стр. 29-36.

17. Хассе Г. Лекции по теории чисел. — М.:ИЛ, 1953. — 527 с.

18. Шафаревич И.Р. Основы алгебраической геометрии. — М.:Наука. — 1972.

19. Anglin W.S. Simultaneous Pell Equations // Math. Comp. — 1996. — V.65, № 213. p.355-359.

20. Baker A. Linear Forms In The Logarithms of Algebraic Numbers // Mathematica. 1968. - V.15. - p.204-216.

21. Baker ADavenport H. The Equations 3x2 2 = y2 and 8x2 - 7 = z2 // The Quaterly Journal of Mathematics, Oxford. — 1969. — V.20, №78.

22. Bennet M.A. On The Number of Solutions of Simultaneous Pell Equations//, Mathematics Subject Classification. — 1991. — preprint.

23. Billet 0., Joye M. The Jacobi Model Of An Elliptic Curve And Side-Channel Analysis. — 2002. — preprint.

24. Brent R.P. Some Integer Factorization Algorithms Using Elliptic Curves // Australian Computer Science Communacations. — 1986. — № 8. — p. 149-163.

25. Brent R.P. Some Integer Factorization Algorithms Using Elliptic Curves. — 1998. — дополненная версия статьи 2 I].

26. Chudnovsky D., Chudnovsky G. Sequences of Numbers Generated by Addition in Formal Groups and New Primality and Factorization tests // Advances in Applied Mathematics. — 1987. — № 7. — p. 385-434.

27. Grinstead C.M. On a Method of Solving a Class of Diophantine Equations // Math. Сотр. 1978. - V.32. - p. 936-940.

28. Davenport H. The Higher Arithmetic. An Introduction to the Theory of Numbers. — NY. — 1952. В русском переводе: Дэвенпорт Г. Высшая арифметика. Введение в теорию чисел. — М.:Наука. — 1965.

29. Dewaghe L. Remarks on the Schoof-Elkies-Atkin algorithm. — Math. Сотр. V.67. - 1998. - p. 1247-1252.

30. Husemoller D. Elliptic Curves. — 2nd Ed. — Springer. — 2004. — 487pp.

31. Lenstra H. W. Factoring Integers with Elliptic Curves // Ann. Math. — 1987. Ш 126. - p.649-673.

32. Lenstra A.K. and Lenstra H. W., Jr. The Development of The Number Field Sieve. — Lecture Notes in Math, 1554. — Springer — 1993.

33. Liardet P., Smart N. Preventing SPA/DMA In ECC Systems Using The Jacobi Form // Cryptographic Hardware and Embedded Systems. — CHES-2001. — Lecture Notes in Computer Science, 2162. — Springer. -2001. -p.391-401.

34. Montgomery P.L. Speeding The Pollard and Elliptic Curve Methods of Factorization // Math, of Comp. — 1987. — Vol. 48. — № 177. — P. 243-267.

35. Montgomery P.L. An FFT Extension of Elliptic Curve Method of Factorization. — University of California. — 1992. — PhD Thesis.

36. Pinch R.G.E. Simultaneous Pell Equations// Math.Proc. Cambridge Philos. Soc. V.103. - 1988. - p.35-46.

37. Pollard J.M. A Monte Carlo Method for Factorisation // BIT. — 1975. № 15. - p.331-334.

38. Pomerance C. The Quadratic Sieve Factoring Algorithm // EUROCRYPT-84. Lecture Notes in Computer Science, 209. -Springer-Verlag. — 1985. - pp. 169-182.

39. Pomerance C. A Tale of Two Sieves// Notices of the AMS. — V.43. — 1996. p.1473-1485.

40. Pomerance C. Two methods in elementary analytic number theory // Number theory and applications / Ed. R.A. Molin. — 1989. — p. 135161.

41. Schoof R. Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p // Math. Comp. — V.44. 1985. - p.483-494.

42. Schoof R. Counting Points On Elliptic Curves Over Finite Fields //J. Theorie des Nombres de Bordeaux. — Vol. 7. — 1995. — p.219-254.

43. Silverman R. The Multiple Polynomial Quadratic Sieve // Math. Of Comp. V.48. - 1987. - p.329-339.

44. Waldschmidt M. A Lower Bound for Linear Forms in Logarithms // Acta Arithmetica. V.37. - 1988. — p.257-283.