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

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

История

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

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

Множество аффинных точек эллиптической кривой $y^{2}=x^{3}-7x+10$ над полем $\mathbb {F} _{q}$ для $q=19,97,127,487$.

Теорема Хассе об эллиптических кривых утверждает, что количество точек $N$ на эллиптической кривой над конечным полем $\mathbb {F} _{q}$ удовлетворяет неравенству $|N-(q+1)|\leqslant 2{\sqrt {q}}$.

Неравенство вытекает из того факта, что $N$ отличается от $q+1$, числа точек на проективной прямой над тем же полем, на сумму двух комплексно-сопряжённых чисел, имеющих модуль ${\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}$.

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

Лемма 1: $d_{-1}-d_{0}-1=N_{p}-p$

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

Согласно формулам сложения имеем $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-1)/2}=\left({\frac {x^{3}+ax+b}{p}}\right)$

потому при сокращении из знаменателя выпадут лишь множители вида $(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$ - одно. Это доказывает требуемое.

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

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

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

$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})$

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

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

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

Мы докажем это неравенство, формально найдя значение функции $X_{n}$ при $x=\infty$. Пусть $m$ есть нуль или первый номер после очередного пробела^{[уточнить]}, $m\geqslant 0$. По построению $X|_{\infty }=\infty$, а $Y|_{\infty }$≠0. Допустим обратное. Ввиду того, что дробь ${\frac {X_{n+1}^{3}+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_{n}x}{X_{n}}}|_{\infty }=1$, ${\frac {Y_{n}^{2}x^{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$. Лемма доказана.

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

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

Основные трудности в доказательстве теоремы сконцентрированы на основной лемме. Приступим к её доказательству. для любого многочлена P символом ст. Р будем обозначать степень этого многочлена.

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

$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^{2}P_{n}^{2})=2d_{n}+2$, потому что в силу леммы 3 старший член многочлена $P_{n-1}P_{n+1}$ совпадает со старшим членом многочлена $x^{2}P_{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}(modE)$,

следует что

$R=2Q_{n}(1-Y_{n})(x^{3}+ax+b)(modE)$,

$S=2Q_{n}(1+Y_{n})(x^{3}+ax+b)(modE)$.

Многочлен $E$, деля многочлен $(xQ_{n}-P_{n})^{2}$, не может делить $Q_{n}$, поскольку $P_{n}$ и $Q_{n}$ взаимно просты. Отсюда и из последних формул вытекает, что $S+R=4Q_{n}^{2}(x^{3}+ax+b)modE$, так что если $E$ делит $R$ и $S$, то $E$ строго делит многочлен $x^{3}+ax+b$(по предположению этот многочлен не имеет кратных корней).

Итак, пусть $E$ - неприводимый делитель многочлена $x^{3}+ax+b$. Предположим сначала, что $Y_{n}$≠±1$(modE)$ (эта запись по определению означает, что числитель несократимого представления функции $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$(modE)$. Пусть, например, $Y_{n}=-1(modE)$ (вторая разбирается аналогично). Тогда $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}(modE)$, $x^{2}+xX_{n}+X_{n}^{2}=3x^{2}+a$≠0$(modE)$, так что $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\leqslant 0$,

так что

$|N-p|\leqslant 2{\sqrt {p}}$. Теорема доказана.

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

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

Для конечного поля $\mathbb {F} _{q}$ с алгебраическим замыканием ${\overline {\mathbb {F} _{q}}}$ вводится отображение:

${\begin{array}{lcl}\phi _{q}:{\overline {\mathbb {F} _{q}}}\rightarrow {\overline {\mathbb {F} _{q}}}\\\qquad x\mapsto x^{q}\end{array}}$

На точки эллиптической кривой $E(\mathbb {F} _{q})$ оно действует следующим образом: $\phi _{q}(x,y)=(x^{q},y^{q})$, $\phi _{q}(\infty )=\infty$.

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

Леммы

Лемма 1. Для эллиптической кривой $E(\mathbb {F} _{q})$ над полем $\mathbb {F} _{q}$ и точек $(x,y)\in E({\overline {\mathbb {F} _{q}}})$ выполняется:

1) $\phi _{q}(x,y)\in E({\overline {\mathbb {F} _{q}}})$,

2) $(x,y)\in E(\mathbb {{F}_{q}} )$ тогда и только тогда, когда $\phi _{q}(x,y)=(x,y)$.

Лемма 2. Для эллиптической кривой $E(\mathbb {F} _{q})$ отображение $\phi _{q}$ является эндоморфизмом кривой $E$ степени $q$, и $\phi _{q}$ не разделяемый.

Лемма 3. Пусть определена эллиптическая кривая $E(\mathbb {F} _{q})$ и $n\geqslant 1$. Тогда

1) $\ker(\phi _{q}-1)=E(\mathbb {F} _{q^{n}})$,

2) $\phi _{q}^{n}-1$ — разделяемый эндоморфизм, и поэтому $|E(\mathbb {F} _{q^{n}})|=\deg(\phi _{q}^{n}-1)$.

Лемма 4. Обозначим $a=q+1-|E(\mathbb {F} _{q})|=q+1-\deg(\phi _{q}-1)$. Пусть $r,s$ — целые числа и $\gcd(s,q)=1$. Тогда $\deg(r\phi _{q}-s)=r^{2}q+s^{2}-rsa$.

Исходя из леммы 4, и поскольку $\deg(r\phi _{q}-s)\geqslant 0$, получается, что

$q{\biggl (}{r \over s}{\biggl )}^{2}-a{\biggl (}{r \over s}{\biggl )}+1\geqslant 0$

для любых $r,s$, где $\gcd(s,q)=1$.

Множество рациональных чисел $r/s$, где $\gcd(s,q)=1$, плотное в $\mathbb {R}$. Отсюда, обозначив $r/s=x$, получаем неравенство $qx^{2}-ax+1\geqslant 0$, верное для всех действительных $x$.

Так как дискриминант полинома меньше или равен нулю, то есть $a^{2}-4q\leqslant 0$, то имеем $|a|\leqslant 2{\sqrt {q}}$.

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

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

Обобщением границы Хассе для алгебраических кривых более высокого рода является граница Хассе — Вейля. Пусть имеется абсолютно неприводимая неособая кривая $C$ рода $g$ над конечным полем $\mathbb {F} _{q}$. Тогда для количества точек $\#C(\mathbb {F} _{q})$ на этой кривой справедливо неравенство

$|\#C(\mathbb {F} _{q})-(q+1)|\leqslant 2g{\sqrt {q}}.$

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

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

Применение

Криптография

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

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

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

Дзета-функцию эллиптической кривой $E$ над полем $\mathbb {F} _{q}$ можно записать в виде

$Z_{E}(t)={1-a_{q}(E)t+qt^{2} \over (1-t)(1-qt)}$,

где $a_{q}=q-N_{q}$, а $N_{q}$ — количество аффинных точек проективной кривой $E$. Гипотеза Римана для кривых над конечными полями утверждает, что все нули функции $\zeta _{E}(s)=Z_{E}(q^{-s})$ лежат на прямой $\operatorname {Re} (s)=1/2$ или, что эквивалентно, удовлетворяют равенству $|q^{s}|={\sqrt {q}}$.

Несложно показать, что для эллиптических кривых эта гипотеза эквивалентна теореме Хассе. Действительно, если $Z_{E}(q^{-s})=0$, то $q^{s}$ является корнем квадратного многочлена $f(u)=u^{2}-a_{q}u+q$, чей дискриминант $a_{q}^{2}-4q\leqslant 0$ по теореме Хассе. Значит, корни $u_{1},u_{2}$ многочлена $f(u)$ комплексно сопряжены и $|q^{s}|=|u_{1}|=|u_{2}|={\sqrt {q}}$, что доказывает гипотезу Римана. И наоборот, из выполнения гипотезы Римана следует равенство $|u_{1}|=|u_{2}|={\sqrt {q}}$, что означает, что корни $u_{1},u_{2}$ комплексно сопряжены, а значит, дискриминант $f(u)$ неположителен, что доказывает теорему Хассе.

Литература

• Hurt, Norman E. (2003), Many Rational Points. Coding Theory and Algebraic Geometry, Mathematics and its Applications, vol. 564, Dordrecht: Kluwer/Springer-Verlag, ISBN 1-4020-1766-9, MR: 2042828,{{citation}}: Википедия:Обслуживание CS1 (лишняя пунктуация) (ссылка)
• Niederreiter, Harald; Xing, Chaoping (2009), Algebraic Geometry in Coding Theory and Cryptography, Princeton: Princeton University Press, ISBN 978-0-6911-0288-7, MR: 2573098,{{citation}}: Википедия:Обслуживание CS1 (лишняя пунктуация) (ссылка)
• Глава V Silverman, Joseph H. (1994), The arithmetic of elliptic curves, Graduate Texts in Mathematics, vol. 106, New York: Springer-Verlag, ISBN 978-0-387-96203-0, MR: 1329092,{{citation}}: Википедия:Обслуживание CS1 (лишняя пунктуация) (ссылка)
• Washington, Lawrence C. (2008), Elliptic Curves. Number Theory and Cryptography, 2nd Ed, Discrete Mathematics and its Applications, Boca Raton: Chapman & Hall/CRC Press, ISBN 978-1-4200-7146-7, MR: 2404461,{{citation}}: Википедия:Обслуживание CS1 (лишняя пунктуация) (ссылка)
• Глава 10 Гельфанд, А.О.; Линник, Ю.В. (1962), Элементарные методы в аналитической теории чисел, Москва: Физматгиз
• Chahal, J.S.; Osserman, B. (2008), The Riemann Hypothesis for Elliptic Curves, Mathematical Association of America