Эллиптическая кривая

Шаблон:Не путать Эллипти́ческая крива́я над полем $K$ — неособая кубическая кривая на проективной плоскости над $\hat{K}$ (алгебраическим замыканием поля $K$), задаваемая уравнением 3-й степени с коэффициентами из поля $K$ и «точкой на бесконечности». В подходящих аффинных координатах её уравнение приводится к видуШаблон:SfnШаблон:Sfn

$y^2+a_{1}xy+a_{3}y=x^3+a_2{x}^2+a_{4}x+a_6,$

в котором используется исторически сложившееся обозначение коэффициентов $a_1,a_2,a_3,a_4,a_6$.

История

Древнейшим дошедшим до нашего времени источником, в котором рассматриваются кубические кривые, является «Арифметика» древнегреческого математика Диофанта. В этой работе ставится задача найти рациональные и нетривиальные решения уравнения $y(6-y)=x^3-x$. Диофант решает эту задачу при помощи подстановки $x=3y-1$.

В 1670-х годах Ньютон, используя приёмы аналитической геометрии, делает попытку классифицировать кубические кривые. В ходе исследований Ньютон заметил, что решение Диофанта состоит, по существу, в пересечении кривой, заданной уравнением $y(6-y)=x^3-x$, с касательной $x=3y-1$. Открытие Ньютона в конечном итоге привело к формулам сложения точек на эллиптической кривой. В XIX веке эллиптические кривые находят применениеШаблон:Уточнить в теории эллиптических функций, которые, в свою очередь, тесно связаны с эллиптическими интегралами. Таким образом, исторически термин «эллиптическая кривая» происходит от термина «эллиптический интеграл».

Каноническая форма

Если характеристика поля $K$ не равна 2 или 3 (что включает поля нулевой характеристики, например поля рациональных чисел $\mathbb{Q}$, вещественных чисел $ℝ$ и комплексных чисел $ℂ$), общее уравнение эллиптической кривой с помощью замены координат приводится к канонической форме

$y^2=x^3+ax+b,$

называемой нормальной формой Вейерштрасса.

В случае если характеристика поля $K$ равна 3, общее уравнение кривой можно привести к одной из следующих двух форм:

• $y^2=x^3+a{x}^2+b$(Шаблон:Не переведено 5);
• $y^2=x^3+ax+b$(суперсингулярная кривая).

Наконец, если характеристика поля $K$ равна 2, общее уравнение кривой можно привести к одной из следующих двух формШаблон:Sfn:

• $y^2+xy=x^3+a{x}^2+b$(несуперсингулярная кривая);
• $y^2+cy=x^3+ax+b$(суперсингулярная кривая).

Во всех указанных случаях коэффициенты $a$ и $b$ (либо $a$, $b$ и $c$) являются элементами поля $K$.

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

Графики кривых Шаблон:Nobr и Шаблон:Nobr

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

Поскольку характеристика поля вещественных чисел — 0, а не 2 или 3, то эллиптическая кривая — плоская кривая, определяемая уравнением вида:

$y^2=x^3+ax+b,$

где $a$ и $b$ — вещественные числа. Этот вид уравнений называется уравнениями Вейерштрасса.

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

$\mathrm{\Delta }=-16(4a^3+27b^2)$

не равен нулюШаблон:Sfn.

Если кривая не имеет особых точек, то её график имеет две связные компоненты, если дискриминант положителен, и одну — если отрицателен. Например, для графиков выше в первом случае дискриминант равен 64, а во втором он равен −368.

Групповой закон

Таким образом, можно ввести групповую операцию «+» на кривой со следующими свойствами: точка в бесконечности (обозначаемая символом $O$) является нейтральным элементом группы, и если прямая пересекает данную кривую в точках $P$, $Q$ и $R^{\prime }$, то $P+Q+R^{\prime }=O$ в группе. Суммой точек $P$ и $Q$ называется точка $R=P+Q$, которая симметрична точке $R^{\prime }$ относительно оси $Ox$. Можно показать, что относительно введённой таким образом операции лежащие на кривой точки и точка $O$ образуют абелеву группу; в частности, свойство ассоциативности операции «+» можно доказать, используя теорему о 9 точках на кубической кривой (кубике)Шаблон:Sfn.

Данная группа может быть описана и алгебраически. Пусть дана кривая $y^2=x^3+ax+b$ над полем $K$ (характеристика которого не равна ни 2, ни 3), и точки $P=(x_P,y_P)$ и $Q=(x_Q,y_Q)$ на кривой; допустим, что $x_P\ne x_Q$. Пусть $s=\frac{y_P-y_Q}{x_P-x_Q}$; так как $K$ — поле, то $s$ строго определено. Тогда мы можем определить $R=P+Q=(x_R,y_R)$ следующим образом:

$x_R=s^2-x_P-x_Q,$

$y_R=-y_P+s(x_P-x_R).$

Если $x_P=x_Q$, то есть два варианта. Если $y_P=-y_Q$, то сумма определена как 0; значит, обратную точку к любой точке на кривой можно найти, отразив её относительно оси $Ox$. Если $y_P=y_Q\ne 0$, то $R=P+P=2P=(x_R,y_R)$ определяется так:

$s=\frac{3x_P^2+a}{2y_P},$

$x_R=s^2-2x_P,$

$y_R=-y_P+s(x_P-x_R).$

Если $y_P=y_Q=0$, то $P+P=O$.

Обратный элемент к точке $P$, обозначаемый $-P$ и такой, что $P+(-P)=0$, в рассмотренной выше группе определяется такШаблон:Sfn:

• Если координата $y_P$ точки $P=(x_P,y_P)$ не равна $0$, то $-P=(x_P,-y_P)$.
• Если $y_P=0$, то $-P=P=(x_P,y_P)$.
• Если $P=O$ — точка на бесконечности, то и $-P=O$.

Точка $Q=nP$, где $n$ целое, определяется (при $n>0$) как $Q=\underset{n}{\underbrace{P+P\dots +P}}$. Если $n<0$, то $Q$ есть обратный элемент к $|n|P$. Если $n=0$, то $Q=0\cdot P=O$. Для примера покажем, как найти точку $Q=4P$: она представляется как $4P=2P+2P$, а точка $2P$ находится по формуле $2P=P+P$Шаблон:Sfn.

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

Эллиптическая кривая над комплексными числами строится как фактор комплексной плоскости по решётке Λ, порождённой фундаментальными периодами ω₁ и ω₂. Показано также 4-кручение, соответствующее решётке 1/4 Λ, содержащей Λ

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

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

${\mathrm{\wp }}^{\prime }(z{)}^2=4\mathrm{\wp }(z{)}^3-g_2\mathrm{\wp }(z)-g_3.$

где $g_2$ и $g_3$ — константы; $\mathrm{\wp }(z)$ — эллиптическая функция Вейерштрасса, а ${\mathrm{\wp }}^{\prime }(z)$ — её производная. Функции Вейерштрасса дважды периодичны, то есть периодичны относительно Шаблон:Нп5 $\mathrm{\Lambda }$, и, следовательно, определены на торе $T=ℂ/\mathrm{\Lambda }$. Этот тор может быть вложен в комплексную проективную плоскость отображением

$z\mapsto (1:\mathrm{\wp }(z):{\mathrm{\wp }}^{\prime }(z)).$

Это отображение — изоморфизм римановых поверхностей, то есть топологически данную эллиптическую кривую можно рассматривать как тор. Если решётка $\mathrm{\Lambda }$ связана с решёткой $c\mathrm{\Lambda }$ умножением на ненулевое комплексное число $c$, то соответствующие кривые изоморфны. Класс изоморфизма эллиптической кривой однозначно определяется её j-инвариантом.

Классы изоморфизма можно рассмотреть более простым образом. Константы $g_2$ и $g_3$, называемые модулярными инвариантами, однозначно определяются решёткой, то есть структурой тора. С другой стороны, уравнение эллиптической кривой можно записать как

$y^2=x(x-1)(x-\lambda ).$

Можно показать, что

$g_2=\frac{4^{1/3}}{3}({\lambda }^2-\lambda +1)$

и

$g_3=\frac{1}{27}(\lambda +1)(2{\lambda }^2-5\lambda +2),$

так что Шаблон:Нп5 равен

$\mathrm{\Delta }=g_2^3-27g_3^2={\lambda }^2(\lambda -1{)}^2.$

Здесь $\lambda$ иногда называют Шаблон:Не переведено 5Шаблон:Sfn.

Представление в виде тора также облегчает понимание точек кручения эллиптической кривой: если решётка Λ порождена фундаментальными периодами ${\omega }_1$ и ${\omega }_2$, то точки $n$-кручения — это классы эквивалентности точек

$\frac{a}{n}{\omega }_1+\frac{b}{n}{\omega }_2,$

где $a$ и $b$ — целые числа от $0$ до $n-1$.

Каждая эллиптическая кривая над комплексными числами имеет девять точек перегиба. На каждой прямой, проходящей через две точки перегиба, лежит третья точка перегиба; 9 точек и 12 прямых, построенных таким образом, образуют конфигурацию Гессе.

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

Если коэффициенты уравнения эллиптической кривой $E$ рациональны, то можно рассматривать множество рациональных точек на такой кривой (включая $O$). Это множество образует подгруппу группы действительных точек (включая $O$) на кривой $E$ с таким же групповым законом сложения точек на кривой. Это можно показать следующим образом: рассмотрим алгебраическую формулу получения координаты суммы двух точек $P$ и $Q$, лежащих на кривой $E$. Если эти точки и коэффициенты уравнения кривой рациональны, то координаты точки $R=P+Q$ тоже будут рациональны, так как $x_R$ и $y_Q$ являются рациональными функциями от коэффициентов кривой $E$ координат точек $P$ и $Q$Шаблон:Sfn.

Порядком точки $P$ на кривой $E$ называется наименьшее натуральное $k$ такое, что $kP=O$.

Для эллиптических кривых над полем рациональных чисел справедлива Шаблон:Нп5: на эллиптической кривой $E$ существует такое конечное множество рациональных точек бесконечного порядка $P_1,P_2,\dots ,P_n$, что любая точка на эллиптической кривой представляется в виде

$P=a_1{P}_1+a_2{P}_2+\dots +a_n{P}_n+Q,$

где $a_1,\dots ,a_n$ — целые числа, однозначно определённые для точки $P$, а $Q$ — точка кручения, являющаяся точкой конечного порядкаШаблон:Sfn. Другими словами, теорема гласит, что если поле $K$ — поле рациональных чисел, то группа $K$-рациональных точек — конечнопорождённая. Это означает, что группа может быть представлена как прямая сумма свободной абелевой группы и конечной подгруппы крученияШаблон:Sfn.

Рангом эллиптической кривой $E$ называется минимальное число рациональных точек бесконечного порядка из теоремы Морделла. Нет общего алгоритма для вычисления ранга свободной подгруппы и, соответственно, ранга эллиптической кривой. Формула для вычисления ранга даётся в гипотезе Бёрча — Свиннертон-Дайера.

На 2024 год эллиптическая кривая с максимальным точно известным рангом, равным 20, описывается уравнением

$y^2+xy+y=x^3-x^2-244537673336319601463803487168961769270757573821859853707x+$

Она была найдена Ноамом Элкисом и Зевом Клагсберном в 2020 году.

Также Элкисом и Клагсберном в 2024 году была найдена следующая эллиптическая кривая:

$y^2+xy=x^3-27006183241630922218434652145297453784768054621836357954737385x+$

$+55258058551342376475736699591118191821521067032535079608372404779149413277716173425636721497.$

О ней известно, что её ранг по крайней мере 29 (и в точности равен 29, если верна обобщённая гипотеза Римана).

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

Эллиптическую кривую $E$ можно определить над конечным полем ${𝔽}_q$, где $q=p^r$, а $p$ — простое.

Точное число точек эллиптической кривой $E$ над полем ${𝔽}_q$ вычислить достаточно трудно, однако теорема Хассе об эллиптических кривых даёт следующую оценкуШаблон:Sfn:

$|\mathrm{\#}E({𝔽}_q)-q-1|⩽2\sqrt{q}.$

Этот факт можно истолковать и доказать с помощью общей теории; см. Локальная дзета-функция, Шаблон:Не переведено 5.

Число точек на конкретной кривой может быть вычислено с помощью алгоритма Шуфа.

Приложения

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

В теории чисел эллиптические кривые были, в частности, использованы Эндрю Джоном Уайлсом (совместно с Ричардом Тейлором) в доказательстве великой теоремы Ферма.

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

Литература

• Клеменс, Г. Мозаика теории комплексных кривых. — М.: Мир, 1984.
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга

Ссылки

• Шаблон:Cite web
• Шаблон:MathWorld
• Шаблон:Статья
• Шаблон:Статья