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

Не следует путать с эллипсом.

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

$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}$, вещественных чисел $\mathbb {R}$ и комплексных чисел $\mathbb {C}$), общее уравнение эллиптической кривой с помощью замены координат приводится к канонической форме

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

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

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

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

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

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

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

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

Графики кривых y² = x³ − x и y² = x³ − x + 1

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

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

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

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

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

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

не равен нулю.

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

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

Добавлением «точки в бесконечности» получается проективный вариант этой кривой. Если $P$ и $Q$ — две точки на кривой, то возможно единственным образом описать третью точку — точку пересечения данной кривой с прямой, проведённой через $P$ и $Q$. Если прямая является касательной к кривой в точке, то такая точка считается дважды. Если прямая параллельна оси ординат, третьей точкой будет точка в бесконечности.

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

Данная группа может быть описана и алгебраически. Пусть дана кривая $y^{2}=x^{3}+ax+b$ над полем $K$ (характеристика которого не равна ни 2, ни 3), и точки $P=(x_{P},y_{P})$ и $Q=(x_{Q},y_{Q})$ на кривой; допустим, что $x_{P}\neq x_{Q}$. Пусть $s={\tfrac {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}\neq 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$, в рассмотренной выше группе определяется так:

• Если координата $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=\underbrace {P+P\dots +P} _{n}$. Если $n<0$, то $Q$ есть обратный элемент к $|n|P$. Если $n=0$, то $Q=0\cdot P=O$. Для примера покажем, как найти точку $Q=4P$: она представляется как $4P=2P+2P$, а точка $2P$ находится по формуле $2P=P+P$.

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

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

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

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

$\wp '(z)^{2}=4\wp (z)^{3}-g_{2}\wp (z)-g_{3}.$

где $g_{2}$ и $g_{3}$ — константы; $\wp (z)$ — эллиптическая функция Вейерштрасса, а $\wp '(z)$ — её производная. Функции Вейерштрасса дважды периодичны, то есть периодичны относительно решётки $\Lambda$, и, следовательно, определены на торе $T=\mathbb {C} /\Lambda$. Этот тор может быть вложен в комплексную проективную плоскость отображением

$z\mapsto {\bigl (}1:\wp (z):\wp '(z){\bigr )}.$

Это отображение — изоморфизм римановых поверхностей, то есть топологически данную эллиптическую кривую можно рассматривать как тор. Если решётка $\Lambda$ связана с решёткой $c\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),$

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

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

Здесь $\lambda$ иногда называют модулярной лямбда-функцией.

Представление в виде тора также облегчает понимание точек кручения эллиптической кривой: если решётка Λ порождена фундаментальными периодами $\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$.

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

Для эллиптических кривых над полем рациональных чисел справедлива теорема Морделла: на эллиптической кривой $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$ — точка кручения, являющаяся точкой конечного порядка. Другими словами, теорема гласит, что если поле $K$ — поле рациональных чисел, то группа $K$-рациональных точек — конечнопорождённая. Это означает, что группа может быть представлена как прямая сумма свободной абелевой группы и конечной подгруппы кручения.

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

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

$y^{2}+xy+y=x^{3}-x^{2}-244\,537\,673\,336\,319\,601\,463\,803\,487\,168\,961\,769\,270\,757\,573\,821\,859\,853\,707\,x+{}$

${}+961\,710\,182\,053\,183\,034\,546\,222\,979\,258\,806\,817\,743\,270\,682\,028\,964\,434\,238\,957\,830\,989\,898\,438\,151\,121\,499\,931.$

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

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

$y^{2}+xy=x^{3}-27\,006\,183\,241\,630\,922\,218\,434\,652\,145\,297\,453\,784\,768\,054\,621\,836\,357\,954\,737\,385\,x+{}$

${}+55\,258\,058\,551\,342\,376\,475\,736\,699\,591\,118\,191\,821\,521\,067\,032\,535\,079\,608\,372\,404\,779\,149\,413\,277\,716\,173\,425\,636\,721\,497.$

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

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

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

Точное число точек эллиптической кривой $E$ над полем $\mathbb {F} _{q}$ вычислить достаточно трудно, однако теорема Хассе об эллиптических кривых даёт следующую оценку:

${\big |}\#E(\mathbb {F} _{q})-q-1{\big |}\leqslant 2{\sqrt {q}}.$

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

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

Приложения

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

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

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

Литература

• Клеменс, Г. Мозаика теории комплексных кривых. — М.: Мир, 1984.
• Коблиц Н. Курс теории чисел и криптографии = A Course in Number Theory and Cryptography. — М.: Научное изд-во «ТВП», 2001. — С. 188—200. — 254 с. — ISBN 5-85484-014-6.
• Острик В. В., Цфасман М. А. Алгебраическая геометрия и теория чисел: рациональные и эллиптические кривые. — М.: МЦНМО, 2001. — С. 48. — (Библиотека «Математическое просвещение»). — ISBN 5-900916-71-5.
• Коблиц Н. Введение в эллиптические кривые и модулярные формы = Introduction to Elliptic Curves and Modular Forms. — Новокузнецк: ИО НФМИ, 2000. — С. 33—37. — 312 с. — ISBN 5-8032-3325-0.
• Ленг С. Эллиптические функции = Elliptic functions. — Новокузнецк: ИО НФМИ, 2000. — С. 312. — ISBN 5-8032-3326-9.
• Joseph H. Silverman. The Arithmetic of Elliptic Curves. — N. Y.: Springer, 2009. — P. 42—43,59,137—138. — 408 p. — ISBN 978-0-387-09493-9.
• Урбанович, П. П. Защита информации методами криптографии, стеганографии и обфускации. — Минск: БГТУ, 2016. — С. 81. — 220 с. — ISBN 978-985-530-562-1.

Ссылки

• 14H52 Elliptic Curves (англ.). The Mathematical Atlas. Дата обращения: 2 января 2015. Архивировано 23 февраля 2003 года.
• Weisstein, Eric W. Elliptic Curves (англ.) на сайте Wolfram MathWorld.
• Николенко С. Эллиптическая криптография // Компьютерра. — 1 сентября 2006.
• Соловьёв Ю. П. Рациональные точки на эллиптических кривых // Соросовский образовательный журнал. — 1997. — № 10. — С. 138—143.