Русская Википедия:Теорема Хассе

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

История

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

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

Файл:Illustration for Hasse's Theorem.png

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

Теорема Хассе об эллиптических кривых утверждает, что количество точек <math>N</math> на эллиптической кривой над конечным полем <math>\mathbb{F}_q</math> удовлетворяет неравенству <math>|N - (q + 1)| \leqslant 2\sqrt{q}</math>.^[3]^[4]

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

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

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

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

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

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

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

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

Лемма 1: <math>d_{-1}-d_0-1=N_p-p</math>

Шаблон:Hider

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

Шаблон:Hider

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

Шаблон:Hider|_\infty=1</math> то есть

<math>\frac{Y_nx}{X_n}|_\infty=1</math>, <math>\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</math>

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

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

так что

<math>\frac{X_{n+1}}{x}|_\infty=-1</math>

Но из этого равенства следует, что <math>Y_{n+1}^2|_\infty</math>, что противоречит сделанному предположению <math>Y_{n+1}^2|_\infty=0</math>. Лемма доказана. }}

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

Шаблон:Hider}{Q_{n-1}Q_{n+1}}=\frac{(xP_n-aQ_n)^2-2b(xQ_n+P_n)}{(xQ_n-P_n)^2}</math> Цель следующих рассуждений - показать, что <math>Q_{n-1}*Q_{n+1}=(xP_n-aQ_n)^2</math>. Из этого равенства напрямую получится основная лемма, в самом деле, тогда следует что

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

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

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

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

<math>P_n=xQ_n(mod E)</math>,

следует что

<math>R=2Q_n(1-Y_n)(x^3+ax+b)(mod E)</math>,

<math>S=2Q_n(1+Y_n)(x^3+ax+b)(mod E)</math>.

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

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

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

<math>(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}</math>.

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

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

<math>(N-p)^2-4p\leqslant0</math>,

так что

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

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

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

Для конечного поля <math>\mathbb{F}_q</math> с алгебраическим замыканием <math>\overline{\mathbb{F}_q}</math> вводится отображение:

<math>\begin{array}{lcl}\phi_q:\overline{\mathbb{F}_q}\rightarrow\overline{\mathbb{F}_q} \\ \qquad x\mapsto x^q \end{array}</math>

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

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

{{Hider|

 title = Леммы |
 hidden = 0 |
 title-style = text-align: left; |
 content-style = text-align: left; |
 content =

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

1) <math>\phi_q (x,y)\in E(\overline{\mathbb{F}_q})</math>,

2) <math>(x,y)\in E(\mathbb{{F}_q})</math> тогда и только тогда, когда <math>\phi_q (x,y) = (x,y)</math>.

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

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

1) <math>\ker(\phi_q - 1) = E(\mathbb{F}_{q^n})</math>,

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

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

Исходя из леммы 4, и поскольку <math>\deg(r\phi_q - s) \geqslant 0</math>, получается, что

<math>q \biggl({r \over s}\biggl)^2 - a\biggl({r \over s}\biggl) + 1 \geqslant 0</math>

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

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

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

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

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

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

<math>|\#C(\mathbb{F}_q) - (q+1)| \leqslant 2g \sqrt{q}.</math>

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

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

Применение

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

Шаблон:Main

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

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

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

<math>Z_E(t) = {1 - a_q(E)t + qt^2 \over (1-t)(1-qt)}</math>,

где <math>a_q = q - N_q</math>, а <math>N_q</math> — количество аффинных точек проективной кривой <math>E</math>. Гипотеза Римана для кривых над конечными полями утверждает, что все нули функции <math>\zeta_E(s) = Z_E(q^{-s})</math> лежат на прямой <math>\operatorname{Re}(s) = 1/2</math> или, что эквивалентно, удовлетворяют равенству <math>|q^s| = \sqrt{q}</math>.

Несложно показать, что для эллиптических кривых эта гипотеза эквивалентна теореме Хассе. Действительно, если <math>Z_E(q^{-s}) = 0</math>, то <math>q^s</math> является корнем квадратного многочлена <math>f(u) = u^2 - a_qu + q</math>, чей дискриминант <math>a_q^2 - 4q \leqslant 0</math> по теореме Хассе. Значит, корни <math>u_1,u_2</math> многочлена <math>f(u)</math> комплексно сопряжены и <math>|q^s| = |u_1| = |u_2| = \sqrt{q}</math>, что доказывает гипотезу Римана. И наоборот, из выполнения гипотезы Римана следует равенство <math>|u_1| = |u_2| = \sqrt{q}</math>, что означает, что корни <math>u_1,u_2</math> комплексно сопряжены, а значит, дискриминант <math>f(u)</math> неположителен, что доказывает теорему Хассе.

Примечания

Шаблон:Примечания

Литература

Шаблон:Кривые

[1] Шаблон:Публикация — MR 1544652 Шаблон:Wayback.

[2] Шаблон:Публикация

[:0-3] Шаблон:Cite web

[:1-4] Шаблон:Публикация

[5] Шаблон:Публикация — MR 0029393 Шаблон:Wayback

[1]

[2]

[3]

[4]

[5]

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.

Русская Википедия:Теорема Хассе

Содержание