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

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

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

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

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

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

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

В криптографии эллиптические кривые рассматриваются над двумя типами конечных полей: простыми полями нечётной характеристики (\mathbb{Z}_p, где p > 3 — простое число) и полями характеристики 2 (GF(2^m)).

 y^2 = x^3 +ax + b   mod(p)

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

D=(x_1-x_2)^2(x_1-x_3)^2(x_2-x_3)^2=-16(4a^3+27b^2)

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

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

(\sqrt q - 1)^2 \leqslant |E(\mathbb{F}_q)| \leqslant (\sqrt q + 1)^2,

что влечёт:

\left| |E(\mathbb{F}_q)|-q\right| < 2\sqrt q + 1.

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

\left| |E(\mathbb{F}_q)|-q-1\right| < 2\sqrt q.

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

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

Y^2 = \frac{X^3+aX+b}{x^3+ax+b}

решения которого ищем в области рациональных функции от переменной x. Два решения этого уравнения просты и равны X=x, Y=1; X=x^p, Y=(x^3+ax+b)^{(p-1)/2}.

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

X_3=-X_1-X_2+\frac{Y_2-Y_1}{X_2-X_1}(x^3+ax+b)
Y_3=\frac{Y_2-Y_1}{X_2-X_1}(X_3-X_1)+Y_1

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

(X_0, Y_0) = (x^p, (x^3+ax+b)^{(p-1)/2})

Каждый элемент последовательности представим в виде несократимого соотношения X_n=\frac{P_n}{Q_n}. Далее введем функцию d_n, равную степени многочлена P_n.


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

Лемма 1: d_{-1}-d_0-1=N_p-p

Основная лемма: d_{n-1}+d_{n+1}=2d_n+2

Лемма 2: d_n=n^2-(d_{-1}-d_0-1)n+d_0


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

Согласно формулам сложения имеем X_{-1}=-x-x^p+\frac{(1+(x^3+ax+b)^{(p-1)/2})^2(x^3+ax+b)}{(x-x^p)^2}, далее заметим что степень числителя больше степени знаменателя на 1[уточнить], то есть X_{-1}=\frac{x^{2p+1}+R(x)}{(x-x^p)^2}, где R(x) - многочлен степени, не превосходящей 2p. Вычислим знаменатель дроби по проведении необходимых сокращений. С одной стороны (x-x^p)^2=(x(x-1)...(x-p+1))^2, с другой, как известно[уточнить],

(x^3+ax+b)^p=\frac{x^3+ax+b}{p}

потому при сокращении из знаменателя выпадут лишь множители вида (x-k)^2 с \frac{k^3+ak+b}{p}=-1, и множители вида (x-l) с l^3+al+b=0. Пусть m-количество множителей первого рода, а n - второго. Тогда d_{-1}=2p-2m-n+1, и учитывая, что d_0=p, получаем d_{-1}-d_0-1=p-2m-n. Число N же равно 2(p-m)-n, так как каждому классу вычетов k соответствует два решения, а классу вычетов l - одно. Это доказывает требуемое.


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

По основной лемме d_{n+2}=2d_{n+1}-d_n+2. Очевидно, что для n=-1 и n=0 лемма верна: пусть она верна и для индексов n и n+1, n\geqslant0. Тогда

d_{n+2}=2d_{n+1}-d_n+2=2((n+1)^2-(d_{-1}-d_0-1)(n+1)+d_0)-n^2+(d_{-1}-d_0-1)n-d_0+2=(n+2)^2-(d_{-1}-d_0-1)(n+2)+d_0)

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


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

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

Мы докажем это неравенство, формально найдя значение функции X_n при x=\infty. Пусть m есть нуль или первый номер после очередного пробела[уточнить], m\geqslant0. По построению[уточнить] X|_{\infty}=\infty, а Y|_{\infty}≠0. Допустим обратное. Ввиду того, что дробь \frac{X^3_{n+1}+aX_{n+1}+b}{x^3+ax+b}, должна быть квадратом, разность степеней числителя и знаменателя функции X_{n+1} должна быть числом нечетным, то вместе с Y_{n+1}|_\infty=0 дает X_{n+1}|_\infty=0. Для арифметической прогрессии следует

Y_{n+1}=\frac{1-Y_n}{X-X_n}(x-X_{n+1})-1

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

\frac{1-Y_n}{x-X_n}(x-X_n)|_\infty=1 или \frac{1-Y_n}{1-\frac{X_n}{x}}|_\infty=1

то есть

\frac{Y_nx}{X_n}|_\infty=1, \frac{Y_n^2x^2}{X_n^2}|_\infty=\frac{(X_n^3+aX_n+b)x^2}{(x^3+ax+b)X_n^2}|_\infty=1

Поскольку X_n|_\infty=x|_\infty=\infty, отсюда следует, что \frac{X_n}{x}|_\infty=1. С другой стороны

X_{n+1}=-x-X_n+\frac{(1-Y_n^2)^2}{(x-X_n)^2}(x^3+ax+b)

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

\frac{X_n}{x}=-1-\frac{X_n}{x}+\frac{(1-Y_n^2)^2}{(1-\frac{X_n}{x})^2}(1+\frac{a}{x^2}+\frac{b}{x^3})

так что

\frac{X_{n+1}}{x}|_\infty=-1

Но из этого равенства следует, что Y_{n+1}^2|_\infty, что противоречит сделанному предположению Y_{n+1}^2|_\infty=0. Лемма доказана. Приводя к общему знаменателю и собирая подобные члены в формуле сложения решений, находим

X_{n-1}=\frac{-(xQ_n+P_n)(xQ_n-P_n)^2+(1+Y_n)^2(x^3+ax+b)Q_n}{(xQ_n-P_n)^2}=\frac{(xQ_n+P_n)(xP_n+aQ_n)+2bQ_n^2+2Y_n(x^3+ax+b)Q_n^2}{(xQ_n-P_n)^2}=\frac{S}{(xQ_n-P_n)^2}

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

X_{n-1}X_{n+1}=\frac{P_{n-1)P_{n+1}}}{Q_{n-1}Q_{n+1}}=\frac{(xP_n-aQ_n)^2-2b(xQ_n+P_n)}{(xQ_n-P_n)^2}

Цель следующих рассуждений - показать, что Q_{n-1}*Q_{n+1}=(xP_n-aQ_n)^2. Из этого равенства напрямую получится основная лемма, в самом деле, тогда следует что

P_{n-1}*P_{n+1}=(xP_n-aQ_n)^2-4bQ_n(xQ_n+P_n),

значит d_{n-1}+d_{n+1}= ст. (P_{n-1}P_{n+1})=ст. (x^2P_n^2)=2d_n+2, потому что в силу леммы 3 старший член многочлена P_{n-1}P_{n+1} совпадает со старшим членом многочлена x^2P_n^2. Теперь докажем нужное равенство.

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

Разобьем все неприводимые делители E многочлена (xQ_n-P_n)^2 на три группы. К первой группе отнесем те многочлены, которые делят R, но не делят S. Из этого сразу же вытекает, что если многочлен E^e строго делит (xQ_n-P_n)^2, то он строго делит знаменатель Q_{n+1} и взаимно просто со знаменателем Q_{n-1}. Ко второй группе отнесем те многочлены >E, которые делят S, но не делят R. Точно так же получается, что если многочлен E^e строго делит (xQ_n-P_n)^2, то он строго делит знаменатель Q_{n-1} и взаимно просто со знаменателем Q_{n+1}. Наконец к третьей группе отнесем те многочлены E, которые делят и R, и S. Поскольку

P_n=xQ_n(mod E),

следует что

R=2Q_n(1-Y_n)(x^3+ax+b)(mod E),
S=2Q_n(1+Y_n)(x^3+ax+b)(mod E).

Многочлен E, деля многочлен (xQ_n-P_n)^2, не может делить Q_n, поскольку P_n и Q_n взаимно просты. Отсюда и из последних формул вытекает, что S+R=4Q_n^2(x^3+ax+b) mod E, так что если E делит R и S, то E строго делит многочлен x^3+ax+b(по предположения этот многочлен не имеет кратных корней).

Итак пусть E неприводимый делитель многочлена x^3+ax+b. Предположим сначала, что Y_n≠±1(mod E) (эта запись по определению означает, что числитель несократимого представления функции Y_n±1 не делится на E). Тогда следует, что E строго делит R, потому что многочлен (xQ_n-P_n)^2 делится по крайней мере на E^2. Подобным образом получается, что E делит S, но тогда вытекает, что E^2 строго делит (xQ_n-P_n)^2.

Таким образом, остается проверить, случаи Y_n+=±1(mod E). Пусть, например, Y_n=-1(mod E) (вторая разбирается аналогично). Тогда E строго делит S. Пусть E^2 строго делит (xQ_n-P_n)^2, а E^{2f+1} строго делит (1+Y_n)(X^3+ax+b)Q_n^2. Очевидно E^{2f} строго делит также функцию (1+Y_n)^2(1-Y_n)^2=(1-Y_n^2)^2. Но

(1-Y_n^2)^2=\frac{(x^3+ax-X_n^2-aX_n^2)^2}{(x^3+ax+b)^2}=\frac{(x-X_n)^2(x^2+xX_n+X_n^2+a)^2}{(x^3+ax+b)^2}.

Кроме того, x=X_n(mod E), x^2+xX_n+X_n^2=3x^2+a≠0(mod E), так что 2f=2e-2 и, следовательно, число 2f+1=2e-1 меньше степени, в которой E строго делит (xQ_n+P_n)(xQ_n-P_n)^2. Поэтому E^{2e} строго делит RS. Откуда вытекает, что E^{2e} строго делит Q_{n-1}Q_{n+1}. Что и требовалось доказать.


Согласно леммам 1 и 2, d_n=n^2-(N-p)n+p, и этот квадратный трехчлен принимает неотрицательные значения для всех n, причем по определению не может иметь двух последовательных нулей. Отсюда имеем что дискриминант не может быть положительным, иначе было 2 корня a, b, между n и n+1, и числа ab и a+b не могут быть одновременно целыми. Следовательно,

(N-p)^2-4p\leqslant0,

так что

|N-p|<2\sqrt p. Теорема доказана.

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

Обобщением границы Хассе для алгебраических кривых более высокого рода является граница Хассе-Вейля. Она устанавливает ограничение на количество точек на кривой над конечным полем. Если число точек на кривой С рода g над конечным полем \mathbb{F}_q есть \#C(\mathbb{F}_q), то

|\#C(\Bbb{F}_q) - (q+1)| \le 2g \sqrt{q}.

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

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

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

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

  1. Artin, Emil (1924), "«Quadratische Körper im Gebiete der höheren Kongruenzen. II. Analytischer Teil»", Mathematische Zeitschrift Т. 19 (1): 207–246, ISSN 0025-5874, DOI 10.1007/BF01181075 
  2. Hasse, Helmut (1936), "«Zur Theorie der abstrakten elliptischen Funktionenkörper. I, II & III»", Crelle's Journal Т. 1936 (175), ISSN 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. Weil, André (1949), "«Numbers of solutions of equations in finite fields»", Bulletin of the American Mathematical Society Т. 55 (5): 497–508, ISSN 0002-9904, doi:10.1090/S0002-9904-1949-09219-4, <http://www.ams.org/bull/1949-55-05/S0002-9904-1949-09219-4/home.html> 
  6. Deligne, Pierre (1974), "«La Conjecture de Weil: I»", Publications Mathématiques de l'IHÉS Т. 43: 273–307, ISSN 0073-8301, doi:10.1007/BF02684373, <http://www.numdam.org/item?id=PMIHES_1974__43__273_0> 

Ссылки[править | править вики-текст]