Эллиптическая кривая - NiNa.Az

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

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

${\displaystyle y^{2}+a_{1}xy+a_{3}y=x^{3}+a_{2}x^{2}+a_{4}x+a_{6},}$

в котором используется исторически сложившееся обозначение коэффициентов ${\displaystyle a_{1},a_{2},a_{3},a_{4},a_{6}}$.

История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle x_{R}=s^{2}-x_{P}-x_{Q},}$

${\displaystyle y_{R}=-y_{P}+s(x_{P}-x_{R}).}$

Если ${\displaystyle x_{P}=x_{Q}}$, то есть два варианта. Если ${\displaystyle y_{P}=-y_{Q}}$, то сумма определена как 0; значит, обратную точку к любой точке на кривой можно найти, отразив её относительно оси ${\displaystyle Ox}$. Если ${\displaystyle y_{P}=y_{Q}\neq 0}$, то ${\displaystyle R=P+P=2P=(x_{R},y_{R})}$ определяется так:

${\displaystyle s={\frac {3x_{P}^{2}+a}{2y_{P}}},}$

${\displaystyle x_{R}=s^{2}-2x_{P},}$

${\displaystyle y_{R}=-y_{P}+s(x_{P}-x_{R}).}$

Если ${\displaystyle y_{P}=y_{Q}=0}$, то ${\displaystyle P+P=O}$.

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

• Если координата ${\displaystyle y_{P}}$ точки ${\displaystyle P=(x_{P},y_{P})}$ не равна ${\displaystyle 0}$, то ${\displaystyle -P=(x_{P},-y_{P})}$.
• Если ${\displaystyle y_{P}=0}$, то ${\displaystyle -P=P=(x_{P},y_{P})}$.
• Если ${\displaystyle P=O}$ — точка на бесконечности, то и ${\displaystyle -P=O}$.

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

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

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

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

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

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

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

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

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

Классы изоморфизма можно рассмотреть более простым образом. Константы ${\displaystyle g_{2}}$ и ${\displaystyle g_{3}}$, называемые , однозначно определяются решёткой, то есть структурой тора. С другой стороны, уравнение эллиптической кривой можно записать как

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

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

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

и

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

так что ^[англ.] равен

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

Здесь ${\displaystyle \lambda }$ иногда называют ^[англ.].

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

${\displaystyle {\frac {a}{n}}\omega _{1}+{\frac {b}{n}}\omega _{2},}$

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

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

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

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

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

Для эллиптических кривых над полем рациональных чисел справедлива ^[англ.]: на эллиптической кривой ${\displaystyle E}$ существует такое конечное множество рациональных точек бесконечного порядка ${\displaystyle P_{1},P_{2},\dots ,P_{n}}$, что любая точка на эллиптической кривой представляется в виде

${\displaystyle P=a_{1}P_{1}+a_{2}P_{2}+\dots +a_{n}P_{n}+Q,}$

где ${\displaystyle a_{1},\dots ,a_{n}}$ — целые числа, однозначно определённые для точки ${\displaystyle P}$, а ${\displaystyle Q}$ — точка кручения, являющаяся точкой конечного порядка. Другими словами, теорема гласит, что если поле ${\displaystyle K}$ — поле рациональных чисел, то группа ${\displaystyle K}$-рациональных точек — конечнопорождённая. Это означает, что группа может быть представлена как прямая сумма свободной абелевой группы и конечной подгруппы кручения.

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

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

${\displaystyle 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+{}}$

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

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

${\displaystyle 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+{}}$

${\displaystyle {}+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, если верна обобщённая гипотеза Римана).

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

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

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

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

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

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

Приложения

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

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

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

Примечания

1. Silverman, 2009, p. 59.
2. Коблиц, 2001, с. 188.
3. Adrian Rice, Ezra Brown. Why Ellipses Are Not Elliptic Curves (англ.) // Mathematics Magazine. — 2012. — Vol. 85, no. 3. — P. 163—176. Архивировано 7 марта 2015 года.
4. Silverman, 2009, p. 42—43,409—410.
5. П. П. Урбанович. Защита информации методами криптографии, стеганографии и обфускации. — Минск: БГТУ, 2016. — С. 81. — 220 с. — ISBN 978-985-530-562-1. Архивировано 14 марта 2022 года.
6. Silverman, 2009, p. 42—43.
7. Острик, 2001, с. 21—24.
8. Коблиц, 2001, с. 188—200.
9. Острик, 2001, с. 24.
10. Коблиц, 2000, с. 33—37.
11. Silverman, 2009, p. 20.
12. Острик, 2001, с. 26.
13. Коблиц, 2001, с. 195.
14. Dujella, Andrej. History of elliptic curves rank records (англ.). Andrej Dujella home page. Дата обращения: 30 августа 2024. Архивировано 30 августа 2024 года.
15. Silverman, 2009, p. 137—138.

Литература

• Клеменс, Г. Мозаика теории комплексных кривых. — М.: Мир, 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. — New York: 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.