Lt304888.ru

Туристические услуги

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

22-10-2023

Перейти к: навигация, поиск

Теорема Хассе об эллиптических кривых, также называемая границей Хассе, даёт оценку числа точек на эллиптической кривой над конечным полем, причём ограничивает значения как сверху, так и снизу. Эта гипотеза была первоначально выдвинута Эмилем Артином в его диссертации.[1] Доказал её Хельмут Хассе в 1933 году и опубликовал в серии статей в 1936 году.[2] Теорема Хассе эквивалентна определению абсолютного значения корней локальной дзета-функции[en] Е. В этом виде её можно рассматривать как аналог гипотезы Римана для поля функций, ассоциированного с эллиптической кривой.

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

Основная статья: Эллиптическая кривая

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

y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_5

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

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

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

Формулировка теоремы

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

что влечёт:

Обычно теоремой Хассе называют более точную оценку:[3][4]

Доказательство

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

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

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

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

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


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

Лемма 1:

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

Лемма 2:


Доказательство первой леммы:

Согласно формулам сложения имеем , далее заметим что степень числителя больше степени знаменателя на 1[уточнить], то есть , где R(x) - многочлен степени, не превосходящей 2p. Вычислим знаменатель дроби по проведении необходимых сокращений. С одной стороны , с другой, как известно[уточнить],

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


Доказательство второй леммы:

По основной лемме . Очевидно, что для и лемма верна: пусть она верна и для индексов и , . Тогда

Лемма доказана.


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

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

Мы докажем это неравенство, формально найдя значение функции при . Пусть есть нуль или первый номер после очередного пробела[уточнить], . По построению[уточнить] , а ≠0. Допустим обратное. Ввиду того, что дробь , должна быть квадратом, разность степеней числителя и знаменателя функции должна быть числом нечетным, то вместе с дает . Для арифметической прогрессии следует

Отсюда находим

или

то есть

,

Поскольку , отсюда следует, что . С другой стороны

Отсюда находим

так что

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

Перемножая почленно две полученные выше формулы и проведя сокращения, получим

Цель следующих рассуждений - показать, что . Из этого равенства напрямую получится основная лемма, в самом деле, тогда следует что

,

значит ст. =ст. , потому что в силу леммы 3 старший член многочлена совпадает со старшим членом многочлена . Теперь докажем нужное равенство.

Напомним, что в области многочленов существует однозначное разложение на неприводимые множители. Пусть - неприводимый многочлен, а - любое целое положительное число. Мы будем говорить, что многочлен делит строго делит некоторую несократимую рациональную функцию, если ее числитель делится на , но не делится на . Для доказательства нужного равенства нужно установить что если многочлен строго делит , то он строго делит также . В самом дела, тогда частное представляет собой многочлен, который взаимно прост с многочленом (xQ_n-P_n)^2. Но поскольку из приведенного уравнения следует, что функция является многочленом, то из предыдущих равенств для <X_{n-1}> и <X_{n+1}>без труда получается, что знаменатели , делят многочлен . Тем самым частное может быть только константой, и эта константа равна единице в силу принятой нормировки старших членов числителей .

Разобьем все неприводимые делители многочлена на три группы. К первой группе отнесем те многочлены, которые делят R, но не делят S. Из этого сразу же вытекает, что если многочлен строго делит , то он строго делит знаменатель и взаимно просто со знаменателем . Ко второй группе отнесем те многочлены , которые делят S, но не делят R. Точно так же получается, что если многочлен строго делит , то он строго делит знаменатель и взаимно просто со знаменателем . Наконец к третьей группе отнесем те многочлены , которые делят и R, и S. Поскольку

,

следует что

,
.

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

Итак пусть неприводимый делитель многочлена . Предположим сначала, что ≠±1 (эта запись по определению означает, что числитель несократимого представления функции ±1 не делится на ). Тогда следует, что строго делит , потому что многочлен делится по крайней мере на . Подобным образом получается, что делит , но тогда вытекает, что строго делит .

Таким образом, остается проверить, случаи =±1. Пусть, например, (вторая разбирается аналогично). Тогда строго делит . Пусть строго делит , а строго делит . Очевидно строго делит также функцию . Но

.

Кроме того, , ≠0, так что и, следовательно, число меньше степени, в которой строго делит . Поэтому строго делит . Откуда вытекает, что строго делит . Что и требовалось доказать.


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

,

так что

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

Граница Хассе-Вейля

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

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

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

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

Примечания

  1. «Quadratische Körper im Gebiete der höheren Kongruenzen. II. Analytischer Teil»", 0025-5874, DOI 10.1007/BF01181075 
  2. «Zur Theorie der abstrakten elliptischen Funktionenkörper. I, II & III»", 0075-4102, DOI 10.1515/crll.1936.175.193 
  3. Hasse’s bound for elliptic curves over finite fields (англ.) на сайте PlanetMath.
  4. ↑ А.А. Болотов, С.Б. Гашков, А.Б. Фролов, А.А. Часовских. Элементарное введение в эллиптическую криптографию. Алгебраические и алгоритмические основы. — М.: КомКнига, 2006. — 328 с. — ISBN 5-484-00443-8.
  5. «Numbers of solutions of equations in finite fields»", 0002-9904, 10.1090/S0002-9904-1949-09219-4, <http://www.ams.org/bull/1949-55-05/S0002-9904-1949-09219-4/home.html> 
  6. «La Conjecture de Weil: I»", 0073-8301, 10.1007/BF02684373, <http://www.numdam.org/item?id=PMIHES_1974__43__273_0> 

Ссылки

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

© 2020–2023 lt304888.ru, Россия, Волжский, ул. Больничная 49, +7 (8443) 85-29-01