Эллиптическая кривая
Эллипти́ческая крива́я над полем [math]\displaystyle{ K }[/math] — неособая кубическая кривая на проективной плоскости над [math]\displaystyle{ \hat{K} }[/math] (алгебраическим замыканием поля [math]\displaystyle{ K }[/math]), задаваемая уравнением 3-й степени с коэффициентами из поля [math]\displaystyle{ K }[/math] и «точкой на бесконечности». В подходящих аффинных координатах её уравнение приводится к виду[1][2]
- [math]\displaystyle{ y^2 + a_1 xy + a_3 y = x^3 + a_2 x^2 + a_4 x + a_6, }[/math]
в котором используется исторически сложившееся обозначение коэффициентов [math]\displaystyle{ a_1, a_2, a_3, a_4, a_6 }[/math].
История
Древнейшим дошедшим до нашего времени источником, в котором рассматриваются кубические кривые, является «Арифметика» древнегреческого математика Диофанта. В этой работе ставится задача найти рациональные и нетривиальные решения уравнения [math]\displaystyle{ y(6 - y) = x^3 - x }[/math]. Диофант решает эту задачу при помощи подстановки [math]\displaystyle{ x = 3y - 1 }[/math].
В 1670-х годах Ньютон, используя приёмы аналитической геометрии, делает попытку классифицировать кубические кривые. В ходе исследований Ньютон заметил, что решение Диофанта состоит, по существу, в пересечении кривой, заданной уравнением [math]\displaystyle{ y(6 - y) = x^3 - x }[/math], с касательной [math]\displaystyle{ x = 3y - 1 }[/math]. Открытие Ньютона в конечном итоге привело к формулам сложения точек на эллиптической кривой. В XIX веке эллиптические кривые находят применение[уточнить] в теории эллиптических функций, которые, в свою очередь, тесно связаны с эллиптическими интегралами. Таким образом, исторически термин «эллиптическая кривая» происходит от термина «эллиптический интеграл»[3].
Каноническая форма
Если характеристика поля [math]\displaystyle{ K }[/math] не равна 2 или 3 (что включает поля нулевой характеристики, например поля рациональных чисел [math]\displaystyle{ \Q }[/math], вещественных чисел [math]\displaystyle{ \R }[/math] и комплексных чисел [math]\displaystyle{ \C }[/math]), общее уравнение эллиптической кривой с помощью замены координат приводится к канонической форме
- [math]\displaystyle{ y^2 = x^3 + ax + b, }[/math]
называемой нормальной формой Вейерштрасса.
В случае если характеристика поля [math]\displaystyle{ K }[/math] равна 3, общее уравнение кривой можно привести к одной из следующих двух форм:
- [math]\displaystyle{ y^2 = x^3 + ax^2 + b\quad }[/math](несуперсингулярная кривая[англ.]);
- [math]\displaystyle{ y^2 = x^3 + ax + b\quad }[/math](суперсингулярная кривая).
Наконец, если характеристика поля [math]\displaystyle{ K }[/math] равна 2, общее уравнение кривой можно привести к одной из следующих двух форм[4][5]:
- [math]\displaystyle{ y^2 + xy = x^3 + ax^2 + b\quad }[/math](несуперсингулярная кривая);
- [math]\displaystyle{ y^2 + cy = x^3 + ax + b\quad }[/math](суперсингулярная кривая).
Во всех указанных случаях коэффициенты [math]\displaystyle{ a }[/math] и [math]\displaystyle{ b }[/math] (либо [math]\displaystyle{ a }[/math], [math]\displaystyle{ b }[/math] и [math]\displaystyle{ c }[/math]) являются элементами поля [math]\displaystyle{ K }[/math].
Эллиптические кривые над вещественными числами
Формальное определение эллиптической кривой требует некоторых знаний в алгебраической геометрии, но некоторые свойства эллиптических кривых над вещественными числами можно описать, используя только знания алгебры и геометрии старших классов школы.
Поскольку характеристика поля вещественных чисел — 0, а не 2 или 3, то эллиптическая кривая — плоская кривая, определяемая уравнением вида:
- [math]\displaystyle{ y^2 = x^3 + ax + b, }[/math]
где [math]\displaystyle{ a }[/math] и [math]\displaystyle{ b }[/math] — вещественные числа. Этот вид уравнений называется уравнениями Вейерштрасса.
Определение эллиптической кривой также требует, чтобы кривая не имела особых точек. Геометрически это значит, что график не должен иметь каспов и самопересечений. Алгебраически, достаточно проверить, что дискриминант
- [math]\displaystyle{ \Delta = -16(4a^3 + 27b^2) }[/math]
не равен нулю[6].
Если кривая не имеет особых точек, то её график имеет две связные компоненты, если дискриминант положителен, и одну — если отрицателен. Например, для графиков выше в первом случае дискриминант равен 64, а во втором он равен −368.
Групповой закон
Добавлением «точки в бесконечности» получается проективный вариант этой кривой[7]. Если [math]\displaystyle{ P }[/math] и [math]\displaystyle{ Q }[/math] — две точки на кривой, то возможно единственным образом описать третью точку — точку пересечения данной кривой с прямой, проведённой через [math]\displaystyle{ P }[/math] и [math]\displaystyle{ Q }[/math]. Если прямая является касательной к кривой в точке, то такая точка считается дважды. Если прямая параллельна оси ординат, третьей точкой будет точка в бесконечности.
Таким образом, можно ввести групповую операцию «+» на кривой со следующими свойствами: точка в бесконечности (обозначаемая символом [math]\displaystyle{ O }[/math]) является нейтральным элементом группы, и если прямая пересекает данную кривую в точках [math]\displaystyle{ P }[/math], [math]\displaystyle{ Q }[/math] и [math]\displaystyle{ R' }[/math], то [math]\displaystyle{ P + Q + R' = O }[/math] в группе. Суммой точек [math]\displaystyle{ P }[/math] и [math]\displaystyle{ Q }[/math] называется точка [math]\displaystyle{ R = P + Q }[/math], которая симметрична точке [math]\displaystyle{ R' }[/math] относительно оси [math]\displaystyle{ Ox }[/math]. Можно показать, что относительно введённой таким образом операции лежащие на кривой точки и точка [math]\displaystyle{ O }[/math] образуют абелеву группу; в частности, свойство ассоциативности операции «+» можно доказать, используя теорему о 9 точках на кубической кривой (кубике)[8].
Данная группа может быть описана и алгебраически. Пусть дана кривая [math]\displaystyle{ y^2 = x^3 + ax + b }[/math] над полем [math]\displaystyle{ K }[/math] (характеристика которого не равна ни 2, ни 3), и точки [math]\displaystyle{ P = (x_P, y_P) }[/math] и [math]\displaystyle{ Q = (x_Q, y_Q) }[/math] на кривой; допустим, что [math]\displaystyle{ x_P \ne x_Q }[/math]. Пусть [math]\displaystyle{ s = \tfrac{y_P - y_Q}{x_P - x_Q} }[/math]; так как [math]\displaystyle{ K }[/math] — поле, то [math]\displaystyle{ s }[/math] строго определено. Тогда мы можем определить [math]\displaystyle{ R = P + Q = (x_R, y_R) }[/math] следующим образом:
- [math]\displaystyle{ x_R = s^2 - x_P - x_Q, }[/math]
- [math]\displaystyle{ y_R = -y_P + s (x_P - x_R). }[/math]
Если [math]\displaystyle{ x_P = x_Q }[/math], то есть два варианта. Если [math]\displaystyle{ y_P = -y_Q }[/math], то сумма определена как 0; значит, обратную точку к любой точке на кривой можно найти, отразив её относительно оси [math]\displaystyle{ Ox }[/math]. Если [math]\displaystyle{ y_P = y_Q \ne 0 }[/math], то [math]\displaystyle{ R = P + P = 2P = (x_R, y_R) }[/math] определяется так:
- [math]\displaystyle{ s = \frac{3x_P^2 + a}{2y_P}, }[/math]
- [math]\displaystyle{ x_R = s^2 - 2x_P, }[/math]
- [math]\displaystyle{ y_R = -y_P + s ( x_P - x_R). }[/math]
Если [math]\displaystyle{ y_P = y_Q = 0 }[/math], то [math]\displaystyle{ P + P = O }[/math].
Обратный элемент к точке [math]\displaystyle{ P }[/math], обозначаемый [math]\displaystyle{ -P }[/math] и такой, что [math]\displaystyle{ P + (-P) = 0 }[/math], в рассмотренной выше группе определяется так[9]:
- Если координата [math]\displaystyle{ y_P }[/math] точки [math]\displaystyle{ P = (x_P, y_P) }[/math] не равна [math]\displaystyle{ 0 }[/math], то [math]\displaystyle{ -P = (x_P, -y_P) }[/math].
- Если [math]\displaystyle{ y_P = 0 }[/math], то [math]\displaystyle{ -P = P = (x_P, y_P) }[/math].
- Если [math]\displaystyle{ P = O }[/math] — точка на бесконечности, то и [math]\displaystyle{ -P = O }[/math].
Точка [math]\displaystyle{ Q = nP }[/math], где [math]\displaystyle{ n }[/math] целое, определяется (при [math]\displaystyle{ n \gt 0 }[/math]) как [math]\displaystyle{ Q = \underbrace{P + P \dots + P}_{n} }[/math]. Если [math]\displaystyle{ n \lt 0 }[/math], то [math]\displaystyle{ Q }[/math] есть обратный элемент к [math]\displaystyle{ |n| P }[/math]. Если [math]\displaystyle{ n = 0 }[/math], то [math]\displaystyle{ Q = 0 \cdot P = O }[/math]. Для примера покажем, как найти точку [math]\displaystyle{ Q = 4P }[/math]: она представляется как [math]\displaystyle{ 4P = 2P + 2P }[/math], а точка [math]\displaystyle{ 2P }[/math] находится по формуле [math]\displaystyle{ 2P = P + P }[/math][10].
Эллиптические кривые над полем комплексных чисел
Эллиптические кривые, определённые над комплексными числами, соответствуют вложениям тора в комплексную проективную плоскость. Точки тора также образуют группу, и соответствие между точками эллиптической кривой и точками тора является изоморфизмом групп.
Определение эллиптических кривых как вложения тора в комплексную проективную плоскость естественным образом следует из одного любопытного свойства эллиптических функций Вейерштрасса, согласно которому они и их первые производные связаны формулой
- [math]\displaystyle{ \wp'(z)^2 = 4\wp(z)^3 - g_2 \wp(z) - g_3. }[/math]
где [math]\displaystyle{ g_2 }[/math] и [math]\displaystyle{ g_3 }[/math] — константы; [math]\displaystyle{ \wp(z) }[/math] — эллиптическая функция Вейерштрасса, а [math]\displaystyle{ \wp'(z) }[/math] — её производная. Функции Вейерштрасса дважды периодичны, то есть периодичны относительно решётки[англ.] [math]\displaystyle{ \Lambda }[/math], и, следовательно, определены на торе [math]\displaystyle{ T = \mathbb{C} / \Lambda }[/math]. Этот тор может быть вложен в комплексную проективную плоскость отображением
- [math]\displaystyle{ z \mapsto \bigl(1: \wp(z): \wp'(z) \bigr). }[/math]
Это отображение — изоморфизм римановых поверхностей, то есть топологически данную эллиптическую кривую можно рассматривать как тор. Если решётка [math]\displaystyle{ \Lambda }[/math] связана с решёткой [math]\displaystyle{ c\Lambda }[/math] умножением на ненулевое комплексное число [math]\displaystyle{ c }[/math], то соответствующие кривые изоморфны. Класс изоморфизма эллиптической кривой однозначно определяется её j-инвариантом.
Классы изоморфизма можно рассмотреть более простым образом. Константы [math]\displaystyle{ g_2 }[/math] и [math]\displaystyle{ g_3 }[/math], называемые модулярными инвариантами, однозначно определяются решёткой, то есть структурой тора. С другой стороны, уравнение эллиптической кривой можно записать как
- [math]\displaystyle{ y^2 = x (x - 1) (x - \lambda). }[/math]
Можно показать, что
- [math]\displaystyle{ g_2 = \frac{4^{1/3}}{3} (\lambda^2 - \lambda+1) }[/math]
и
- [math]\displaystyle{ g_3 = \frac{1}{27} (\lambda + 1) (2 \lambda^2 - 5 \lambda + 2), }[/math]
так что модулярный дискриминант[англ.] равен
- [math]\displaystyle{ \Delta = g_2^3 - 27 g_3^2 = \lambda^2 (\lambda - 1)^2. }[/math]
Здесь [math]\displaystyle{ \lambda }[/math] иногда называют модулярной лямбда-функцией[англ.][11].
Представление в виде тора также облегчает понимание точек кручения эллиптической кривой: если решётка Λ порождена фундаментальными периодами [math]\displaystyle{ \omega_1 }[/math] и [math]\displaystyle{ \omega_2 }[/math], то точки [math]\displaystyle{ n }[/math]-кручения — это классы эквивалентности точек
- [math]\displaystyle{ \frac{a}{n} \omega_1 + \frac{b}{n} \omega_2, }[/math]
где [math]\displaystyle{ a }[/math] и [math]\displaystyle{ b }[/math] — целые числа от [math]\displaystyle{ 0 }[/math] до [math]\displaystyle{ n - 1 }[/math].
Каждая эллиптическая кривая над комплексными числами имеет девять точек перегиба. На каждой прямой, проходящей через две точки перегиба, лежит третья точка перегиба; 9 точек и 12 прямых, построенных таким образом, образуют конфигурацию Гессе.
Эллиптические кривые над полем рациональных чисел
Если коэффициенты уравнения эллиптической кривой [math]\displaystyle{ E }[/math] рациональны, то можно рассматривать множество рациональных точек на такой кривой (включая [math]\displaystyle{ O }[/math]). Это множество образует подгруппу группы действительных точек (включая [math]\displaystyle{ O }[/math]) на кривой [math]\displaystyle{ E }[/math] с таким же групповым законом сложения точек на кривой. Это можно показать следующим образом: рассмотрим алгебраическую формулу получения координаты суммы двух точек [math]\displaystyle{ P }[/math] и [math]\displaystyle{ Q }[/math], лежащих на кривой [math]\displaystyle{ E }[/math]. Если эти точки и коэффициенты уравнения кривой рациональны, то координаты точки [math]\displaystyle{ R = P + Q }[/math] тоже будут рациональны, так как [math]\displaystyle{ x_R }[/math] и [math]\displaystyle{ y_Q }[/math] являются рациональными функциями от коэффициентов кривой [math]\displaystyle{ E }[/math] координат точек [math]\displaystyle{ P }[/math] и [math]\displaystyle{ Q }[/math][12].
Порядком точки [math]\displaystyle{ P }[/math] на кривой [math]\displaystyle{ E }[/math] называется наименьшее натуральное [math]\displaystyle{ k }[/math] такое, что [math]\displaystyle{ kP = O }[/math].
Для эллиптических кривых над полем рациональных чисел справедлива теорема Морделла[англ.]: на эллиптической кривой [math]\displaystyle{ E }[/math] существует такое конечное множество рациональных точек бесконечного порядка [math]\displaystyle{ P_1, P_2, \dots, P_n }[/math], что любая точка на эллиптической кривой представляется в виде
- [math]\displaystyle{ P = a_1 P_1 + a_2 P_2 + \dots + a_n P_n + Q, }[/math]
где [math]\displaystyle{ a_1, \dots, a_n }[/math] — целые числа, однозначно определённые для точки [math]\displaystyle{ P }[/math], а [math]\displaystyle{ Q }[/math] — точка кручения, являющаяся точкой конечного порядка[13]. Другими словами, теорема гласит, что если поле [math]\displaystyle{ K }[/math] — поле рациональных чисел, то группа [math]\displaystyle{ K }[/math]-рациональных точек — конечнопорождённая. Это означает, что группа может быть представлена как прямая сумма свободной абелевой группы и конечной подгруппы кручения[14].
Рангом эллиптической кривой [math]\displaystyle{ E }[/math] называется минимальное число рациональных точек бесконечного порядка из теоремы Морделла. Нет общего алгоритма для вычисления ранга свободной подгруппы и, соответственно, ранга эллиптической кривой. Формула для вычисления ранга даётся в гипотезе Бёрча — Свиннертон-Дайера.
На 2021 год эллиптическая кривая с максимальным точно известным рангом описывается следующим уравнением:
- [math]\displaystyle{ y^2 + xy + y = x^3 - x^2 + 244\,537\,673\,336\,319\,593\,869\,425\,922\,560\,705\,080\,346\,187\,029\,821\,884\,727\,296\,x + {} }[/math]
- [math]\displaystyle{ {} + 961\,710\,182\,053\,183\,065\,594\,960\,663\,427\,254\,473\,101\,251\,575\,779\,322\,143\,245\,281\,237\,214\,744\,033\,906\,994\,970\,624. }[/math]
Её ранг равен 20, она была найдена Ноамом Элкисом и Зевом Клагсберном в 2020 году[15]. Про следующую кривую, найденную Элкисом в 2006 году и описываемую уравнением
- [math]\displaystyle{ y^2 + xy + y = x^3 - x^2 + 20\,067\,762\,415\,575\,526\,585\,033\,208\,209\,338\,542\,750\,930\,230\,312\,178\,956\,502\,x + {} }[/math]
- [math]\displaystyle{ {} + 34\,481\,611\,795\,030\,556\,467\,032\,985\,690\,390\,720\,374\,855\,944\,359\,319\,180\,361\,266\,008\,296\,291\,939\,448\,732\,243\,429, }[/math]
известно, что её ранг по крайней мере 28, однако точный ранг этой кривой неизвестен[16]. В 2016 году было опубликовано доказательство того, что ранг этой кривой равен в точности 28, если верна обобщённая гипотеза Римана[17].
Эллиптические кривые над конечными полями
Эллиптическую кривую [math]\displaystyle{ E }[/math] можно определить над конечным полем [math]\displaystyle{ \mathbb{F}_q }[/math], где [math]\displaystyle{ q = p^r }[/math], а [math]\displaystyle{ p }[/math] — простое.
Точное число точек эллиптической кривой [math]\displaystyle{ E }[/math] над полем [math]\displaystyle{ \mathbb{F}_q }[/math] вычислить достаточно трудно, однако теорема Хассе об эллиптических кривых даёт следующую оценку[18]:
- [math]\displaystyle{ \big| \#E(\mathbb{F}_q) - q - 1 \big| \leqslant 2 \sqrt{q}. }[/math]
Этот факт можно истолковать и доказать с помощью общей теории; см. Локальная дзета-функция, Этальные когомологии[англ.].
Число точек на конкретной кривой может быть вычислено с помощью алгоритма Шуфа.
Приложения
Эллиптические кривые над конечными полями используются в некоторых криптографических приложениях для факторизации и тестирования простоты чисел. Обычно основная идея, заложенная в этих приложениях, заключается в том, что известный алгоритм, используемый для конкретных конечных групп, переписывается для использования групп рациональных точек эллиптических кривых.
В теории чисел эллиптические кривые были, в частности, использованы Эндрю Джоном Уайлсом (совместно с Ричардом Тейлором) в доказательстве великой теоремы Ферма.
В криптографии они образуют самостоятельный раздел эллиптической криптографии, посвящённый изучению криптосистем на базе эллиптических кривых. В частности, на эллиптических кривых основаны российские стандарты ГОСТ Р 34.10-2001 и сменивший его ГОСТ Р 34.10-2012, описывающие алгоритмы формирования и проверки электронной цифровой подписи.
Примечания
- ↑ Silverman, 2009, p. 59.
- ↑ Коблиц, 2001, с. 188.
- ↑ Adrian Rice, Ezra Brown. Why Ellipses Are Not Elliptic Curves (англ.) // Mathematics Magazine. — 2012. — Vol. 85, no. 3. — P. 163—176.
- ↑ Silverman, 2009, p. 42—43,409—410.
- ↑ П. П. Урбанович. Защита информации методами криптографии, стеганографии и обфускации. — Минск: БГТУ, 2016. — С. 81. — 220 с. — ISBN 978-985-530-562-1.
- ↑ Silverman, 2009, p. 42—43.
- ↑ Коблиц, 2001, с. 192.
- ↑ Острик, 2001, с. 21—24.
- ↑ Коблиц, 2001, с. 188—200.
- ↑ Острик, 2001, с. 24.
- ↑ Коблиц, 2000, с. 33—37.
- ↑ Silverman, 2009, p. 20.
- ↑ Острик, 2001, с. 26.
- ↑ Коблиц, 2001, с. 195.
- ↑ Dujella, Andrej. History of elliptic curves rank records (англ.). Andrej Dujella home page. Дата обращения: 1 декабря 2021.
- ↑ Dujella, Andrej. Construction of high rank elliptic curves and related Diophantine problems. 7th Symposium on Algebra and Computation (AC 2007). 2007.
- ↑ Klagsbrun, Zev, Travis Sherman, and James Weigandt. The Elkies curve has rank 28 subject only to GRH. arXiv preprint arXiv:1606.07178 (2016).
- ↑ 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. — 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.