Теорема Хассе

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Теорема Хассе об эллиптических кривых, также называемая границей Хассе, даёт оценку числа точек на эллиптической кривой над конечным полем, причём ограничивает значения как сверху, так и снизу. Теорема Хассе эквивалентна определению абсолютного значения корней локальной дзета-функции Е. В этом виде её можно рассматривать как аналог гипотезы Римана для поля функций, ассоциированного с эллиптической кривой.

История[править | править код]

Важным аспектом в применении эллиптических кривых является получение эффективного алгоритма подсчёта количества точек эллиптической кривой. История этого вопроса началась в 20 веке, с предположения Пуанкаре о том, что количество рациональных точек на кривой порядка 1 конечно. Это предположение было доказано Луисом Джоэл Морделлом в 1922 году[1].

В 1924 году Эмиль Артин выдвинул гипотезу об оценке числа этих точек сверху и снизу[2].

Доказал эту гипотезу Хельмут Хассе в 1933 году и опубликовал в серии статей в 1936 году[3].

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

Эллиптические кривые над конечными полями[править | править код]

Эллиптической кривой называется множество точек , удовлетворяющих уравнению:

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

В криптографии используются эллиптические кривые, определённые над полем частных кольца целых p-адических чисел, где в общем случае ,  — простое, и  — целые числа, не делящиесся на , и .[источник не указан 158 дней] Для таких кривых бывает необходимым знание количества точек, лежащих на этих кривых. Точное число этих точек вычислить достаточно трудно, однако теорема Хассе даёт достаточно точную оценку этого числа, как сверху, так и снизу.

Чаще всего рассматриваются эллиптические кривые в форме Вейерштрасса над двумя типами конечных полей: простыми полями нечётной характеристики (, где  — простое число) и полями характеристики 2 ().

Также важной особенностью кривых, используемых в криптографии, является положительность дискриминанта

Формулировка теоремы[править | править код]

Количество точек кривой для .

Теорема Хассе об эллиптических кривых утверждает, что количество точек на эллиптической кривой над конечным полем лежит в интервале: [4][5]

Или же, что то же самое, что это число близко к числу точек на проективной прямой над тем же полем: [4][5]

Доказательство[править | править код]

В ходе доказательства важнейшую роль будет играть видоизмененное уравнение

решения которого ищем в области рациональных функции от переменной . Два решения этого уравнения просты и равны ; .

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

Далее построим бесконечную последовательность решений, которая представляет собой арифметическую прогрессию с разностью и начальным членом

Каждый элемент последовательности представим в виде несократимого соотношения . Далее введем функцию , равную степени многочлена .

Для доказательства нам потребуются 4 леммы:

Лемма 1:

Лемма 2:

Лемма 3: Для всех n, для которых функция Xn определена, имеет место неравенство ст. Рn > ст. Qn.

Основная лемма: .

Согласно леммам 1 и 2, , и этот квадратный трехчлен принимает неотрицательные значения для всех , причем по определению не может иметь двух последовательных нулей. Отсюда имеем, что дискриминант не может быть положительным, иначе было 2 корня , между и , и числа и не могут быть одновременно целыми. Следовательно,

,

так что

. Теорема доказана.

Доказательство при помощи эндоморфизма Фробениуса[править | править код]

Существует альтернативное доказательство теоремы Хассе, в основе которого лежит использование эндоморфизма Фробениуса.

Для конечного поля с алгебраическим замыканием вводится отображение:

На точки эллиптической кривой оно действует, как: .

Для доказательства используются следующие 4 леммы:

Исходя из леммы 4, и поскольку , получается, что

, для любых , где .

Множество рациональных чисел , где плотное в . Отсюда, обозначив , получаем неравенство , верное для всех действительных .

Так как дискриминант полинома меньше или равен нулю, то есть , то отсюда следует, что .

Доказательство теоремы Хассе на основе эндоморфизма Фробениуса также лежит в основе алгоритма Шуфа. Данный алгоритм позволяет подсчитать количество точек для конкретно заданной эллиптической кривой за полиномиальное время.

Граница Хассе-Вейля[править | править код]

Обобщением границы Хассе для алгебраических кривых более высокого рода является граница Хассе-Вейля. Она устанавливает ограничение на количество точек на кривой над конечным полем. Если число точек на кривой С рода g над конечным полем есть , то

Этот результат также эквивалентен определению абсолютного значения корней локальной дзета-функции С, и является аналогом гипотезы Римана для поля функций, ассоциированного с кривой.

В случае эллиптических кривых граница Хассе-Вейля сводится к обычной границе Хассе, так как эллиптические кривые имеют род g=1.

Граница Хассе-Вейля является следствием гипотез Вейля, первоначально предложенных А. Вейлем в 1949 году[6]. Доказательства были предоставлены Пьером Делинем в 1974 году[7].

Применение[править | править код]

Криптография[править | править код]

В криптографии используются алгоритмы шифрования, основанные на эллиптических кривых.

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

В частности, один из таких алгоритмов используется для формирования и проверки электронной цифровой подписи в российском стандарте ГОСТ Р 34.10-2012. В нём используются эллиптические кривые Вейерштрасса в общей форме, a лежит в пределах .

Национальный институт стандартов и технологий (NIST) рекомендует использовать числа вида для быстрого деления по модулю. Так же, по причине эффективной программной реализации рекомендуется использование конкретных конечных полей и эллиптических кривых в этих полях. В частности, FIPS 186-3[8]рекомендует 10 конечных полей. Некоторые из них:

  • поля , где простое p имеет длину 192, 224, 256, 384 или 521 бит,
  • поля , где m = 163, 233, 283, 409 или 571.

Связь с локальной дзета-функцией Римана[править | править код]

Существует гипотеза Римана для кривых над конечным полем. В ней рассматривается зета-функция, задаваемая формулой , где , а — количество точек эллиптической кривой над полем .

Для неё утверждается, что если , тогда .

Доказательство этого факта легко получить, рассмотрев ограничения на величину . Однако этот результат уже известен из теоремы Хассе, откуда мы получаем, что .

Отсюда легко видно, что если , то является корнем уравнения с дискриминантом .

Тогда для корней выполняется , откуда с учётом теоремы Хассе очевидно, что и .

Диофантовы уравнения[править | править код]

Предположение Пуанкаре о конечности рациональных точек на кривой порядка 1, являющееся предпосылкой теоремы Хассе, также нашло своё применение в решении диофантовых уравнений.

В 1922 году Луис Морделл связал множество решений диофантова алгебраического уравнения с геометрическим родом кривой, задаваемой этим уравнением. В процессе анализа уравнения , где - целое число, он пришел к выводу, что для уравнений достаточно высокой степени размерность пространства решений выражается через род кривой, и потому эта размерность конечна[9].

Примечания[править | править код]

  1. Min R. Nevanlinna Theory And Its Relation To Diophantine Approximation. — Singapore : World Scientific, 2001. — 340 p. — ISBN 9814492485. — ISBN 9789814492485.
  2. Artin, Emil. Quadratische Körper im Gebiete der höheren Kongruenzen. II. Analytischer Teil // Mathematische Zeitschrift : journal. — Luxemburg : Springer-Verlag, 1924. — Vol. 19, no. 1. — P. 207–246. — ISSN 0025-5874. — DOI:10.1007/BF01181075. — Zbl 51.0144.05.MR 1544652.
  3. Hasse, Helmut. Zur Theorie der abstrakten elliptischen Funktionenkörper. I, II & III // Crelle's Journal : journal. — Berlin : Walter de Gruyter, 1936. — Vol. 1936, no. 175. — ISSN 0075-4102. — DOI:10.1515/crll.1936.175.193. — Zbl 0014.14903.
  4. 1 2 Hasse’s bound for elliptic curves over finite fields. PlanetMath. Проверено 18 декабря 2017.
  5. 1 2 Болотов А. А., Гашков С. Б., Фролов А. Б., Часовских А. А. Элементарное введение в эллиптическую криптографию : Алгебраические и алгоритмические основы. — М. : КомКнига, 2006. — Т. 1. — 328 с. — ISBN 5-484-00443-8.
  6. Weil, André. Numbers of solutions of equations in finite fields // Bulletin of the American Mathematical Society : journal. — N. Y. : American Mathematical Society, 1949. — Vol. 55, no. 5. — P. 497–508. — ISSN 0002-9904. — DOI:10.1090/S0002-9904-1949-09219-4.MR 0029393.
  7. Deligne, Pierre. La Conjecture de Weil: I // Publications Mathématiques de l'IHÉS : journal. — Bures-sur-Yvette : Institut des hautes études scientifiques, 1974. — Vol. 43. — P. 273–307. — ISSN 0073-8301. — DOI:10.1007/BF02684373. — Zbl 0287.14001. — MR 340258.
  8. FIPS 186-3 Архивировано 7 октября 2013 года. // NIST, 2009; устарел в 2013 году с выходом FIPS 186-4
  9. Mordell L. J. Diophantine Equations. — L.N. Y. : Academic Press, 1969. — Vol. 30. — 311 p. — ISBN 0080873421. — ISBN 9780080873428.

Литература[править | править код]