Русская Википедия:Эллиптическая кривая
Шаблон:Не путать Эллипти́ческая крива́я над полем <math>K</math> — неособая кубическая кривая на проективной плоскости над <math>\hat{K}</math> (алгебраическим замыканием поля <math>K</math>), задаваемая уравнением 3-й степени с коэффициентами из поля <math>K</math> и «точкой на бесконечности». В подходящих аффинных координатах её уравнение приводится к видуШаблон:SfnШаблон:Sfn
- <math>y^2 + a_1 xy + a_3 y = x^3 + a_2 x^2 + a_4 x + a_6,</math>
в котором используется исторически сложившееся обозначение коэффициентов <math>a_1, a_2, a_3, a_4, a_6</math>.
История
Древнейшим дошедшим до нашего времени источником, в котором рассматриваются кубические кривые, является «Арифметика» древнегреческого математика Диофанта. В этой работе ставится задача найти рациональные и нетривиальные решения уравнения <math>y(6 - y) = x^3 - x</math>. Диофант решает эту задачу при помощи подстановки <math>x = 3y - 1</math>.
В 1670-х годах Ньютон, используя приёмы аналитической геометрии, делает попытку классифицировать кубические кривые. В ходе исследований Ньютон заметил, что решение Диофанта состоит, по существу, в пересечении кривой, заданной уравнением <math>y(6 - y) = x^3 - x</math>, с касательной <math>x = 3y - 1</math>. Открытие Ньютона в конечном итоге привело к формулам сложения точек на эллиптической кривой. В XIX веке эллиптические кривые находят применениеШаблон:Уточнить в теории эллиптических функций, которые, в свою очередь, тесно связаны с эллиптическими интегралами. Таким образом, исторически термин «эллиптическая кривая» происходит от термина «эллиптический интеграл»[1].
Каноническая форма
Если характеристика поля <math>K</math> не равна 2 или 3 (что включает поля нулевой характеристики, например поля рациональных чисел <math>\Q</math>, вещественных чисел <math>\R</math> и комплексных чисел <math>\C</math>), общее уравнение эллиптической кривой с помощью замены координат приводится к канонической форме
- <math>y^2 = x^3 + ax + b,</math>
называемой нормальной формой Вейерштрасса.
В случае если характеристика поля <math>K</math> равна 3, общее уравнение кривой можно привести к одной из следующих двух форм:
- <math>y^2 = x^3 + ax^2 + b\quad</math>(Шаблон:Не переведено 5);
- <math>y^2 = x^3 + ax + b\quad</math>(суперсингулярная кривая).
Наконец, если характеристика поля <math>K</math> равна 2, общее уравнение кривой можно привести к одной из следующих двух формШаблон:Sfn[2]:
- <math>y^2 + xy = x^3 + ax^2 + b\quad</math>(несуперсингулярная кривая);
- <math>y^2 + cy = x^3 + ax + b\quad</math>(суперсингулярная кривая).
Во всех указанных случаях коэффициенты <math>a</math> и <math>b</math> (либо <math>a</math>, <math>b</math> и <math>c</math>) являются элементами поля <math>K</math>.
Эллиптические кривые над вещественными числами
Формальное определение эллиптической кривой требует некоторых знаний в алгебраической геометрии, но некоторые свойства эллиптических кривых над вещественными числами можно описать, используя только знания алгебры и геометрии старших классов школы.
Поскольку характеристика поля вещественных чисел — 0, а не 2 или 3, то эллиптическая кривая — плоская кривая, определяемая уравнением вида:
- <math>y^2 = x^3 + ax + b,</math>
где <math>a</math> и <math>b</math> — вещественные числа. Этот вид уравнений называется уравнениями Вейерштрасса.
Определение эллиптической кривой также требует, чтобы кривая не имела особых точек. Геометрически это значит, что график не должен иметь каспов и самопересечений. Алгебраически, достаточно проверить, что дискриминант
- <math>\Delta = -16(4a^3 + 27b^2)</math>
не равен нулюШаблон:Sfn.
Если кривая не имеет особых точек, то её график имеет две связные компоненты, если дискриминант положителен, и одну — если отрицателен. Например, для графиков выше в первом случае дискриминант равен 64, а во втором он равен −368.
Групповой закон
Добавлением «точки в бесконечности» получается проективный вариант этой кривойШаблон:Sfn. Если <math>P</math> и <math>Q</math> — две точки на кривой, то возможно единственным образом описать третью точку — точку пересечения данной кривой с прямой, проведённой через <math>P</math> и <math>Q</math>. Если прямая является касательной к кривой в точке, то такая точка считается дважды. Если прямая параллельна оси ординат, третьей точкой будет точка в бесконечности.
Таким образом, можно ввести групповую операцию «+» на кривой со следующими свойствами: точка в бесконечности (обозначаемая символом <math>O</math>) является нейтральным элементом группы, и если прямая пересекает данную кривую в точках <math>P</math>, <math>Q</math> и <math>R'</math>, то <math>P + Q + R' = O</math> в группе. Суммой точек <math>P</math> и <math>Q</math> называется точка <math>R = P + Q</math>, которая симметрична точке <math>R'</math> относительно оси <math>Ox</math>. Можно показать, что относительно введённой таким образом операции лежащие на кривой точки и точка <math>O</math> образуют абелеву группу; в частности, свойство ассоциативности операции «+» можно доказать, используя теорему о 9 точках на кубической кривой (кубике)Шаблон:Sfn.
Данная группа может быть описана и алгебраически. Пусть дана кривая <math>y^2 = x^3 + ax + b</math> над полем <math>K</math> (характеристика которого не равна ни 2, ни 3), и точки <math>P = (x_P, y_P)</math> и <math>Q = (x_Q, y_Q)</math> на кривой; допустим, что <math>x_P \ne x_Q</math>. Пусть <math>s = \tfrac{y_P - y_Q}{x_P - x_Q}</math>; так как <math>K</math> — поле, то <math>s</math> строго определено. Тогда мы можем определить <math>R = P + Q = (x_R, y_R)</math> следующим образом:
- <math>x_R = s^2 - x_P - x_Q,</math>
- <math>y_R = -y_P + s (x_P - x_R).</math>
Если <math>x_P = x_Q</math>, то есть два варианта. Если <math>y_P = -y_Q</math>, то сумма определена как 0; значит, обратную точку к любой точке на кривой можно найти, отразив её относительно оси <math>Ox</math>. Если <math>y_P = y_Q \ne 0</math>, то <math>R = P + P = 2P = (x_R, y_R)</math> определяется так:
- <math>s = \frac{3x_P^2 + a}{2y_P},</math>
- <math>x_R = s^2 - 2x_P,</math>
- <math>y_R = -y_P + s ( x_P - x_R).</math>
Если <math>y_P = y_Q = 0</math>, то <math>P + P = O</math>.
Обратный элемент к точке <math>P</math>, обозначаемый <math>-P</math> и такой, что <math>P + (-P) = 0</math>, в рассмотренной выше группе определяется такШаблон:Sfn:
- Если координата <math>y_P</math> точки <math>P = (x_P, y_P)</math> не равна <math>0</math>, то <math>-P = (x_P, -y_P)</math>.
- Если <math>y_P = 0</math>, то <math>-P = P = (x_P, y_P)</math>.
- Если <math>P = O</math> — точка на бесконечности, то и <math>-P = O</math>.
Точка <math>Q = nP</math>, где <math>n</math> целое, определяется (при <math>n > 0</math>) как <math>Q = \underbrace{P + P \dots + P}_{n}</math>. Если <math>n < 0</math>, то <math>Q</math> есть обратный элемент к <math>|n| P</math>. Если <math>n = 0</math>, то <math>Q = 0 \cdot P = O</math>. Для примера покажем, как найти точку <math>Q = 4P</math>: она представляется как <math>4P = 2P + 2P</math>, а точка <math>2P</math> находится по формуле <math>2P = P + P</math>Шаблон:Sfn.
Эллиптические кривые над полем комплексных чисел
Эллиптические кривые, определённые над комплексными числами, соответствуют вложениям тора в комплексную проективную плоскость. Точки тора также образуют группу, и соответствие между точками эллиптической кривой и точками тора является изоморфизмом групп.
Определение эллиптических кривых как вложения тора в комплексную проективную плоскость естественным образом следует из одного любопытного свойства эллиптических функций Вейерштрасса, согласно которому они и их первые производные связаны формулой
- <math>\wp'(z)^2 = 4\wp(z)^3 - g_2 \wp(z) - g_3.</math>
где <math>g_2</math> и <math>g_3</math> — константы; <math>\wp(z)</math> — эллиптическая функция Вейерштрасса, а <math>\wp'(z)</math> — её производная. Функции Вейерштрасса дважды периодичны, то есть периодичны относительно Шаблон:Нп5 <math>\Lambda</math>, и, следовательно, определены на торе <math>T = \mathbb{C} / \Lambda</math>. Этот тор может быть вложен в комплексную проективную плоскость отображением
- <math>z \mapsto \bigl(1: \wp(z): \wp'(z) \bigr).</math>
Это отображение — изоморфизм римановых поверхностей, то есть топологически данную эллиптическую кривую можно рассматривать как тор. Если решётка <math>\Lambda</math> связана с решёткой <math>c\Lambda</math> умножением на ненулевое комплексное число <math>c</math>, то соответствующие кривые изоморфны. Класс изоморфизма эллиптической кривой однозначно определяется её j-инвариантом.
Классы изоморфизма можно рассмотреть более простым образом. Константы <math>g_2</math> и <math>g_3</math>, называемые модулярными инвариантами, однозначно определяются решёткой, то есть структурой тора. С другой стороны, уравнение эллиптической кривой можно записать как
- <math>y^2 = x (x - 1) (x - \lambda).</math>
Можно показать, что
- <math>g_2 = \frac{4^{1/3}}{3} (\lambda^2 - \lambda+1)</math>
и
- <math>g_3 = \frac{1}{27} (\lambda + 1) (2 \lambda^2 - 5 \lambda + 2),</math>
так что Шаблон:Нп5 равен
- <math>\Delta = g_2^3 - 27 g_3^2 = \lambda^2 (\lambda - 1)^2.</math>
Здесь <math>\lambda</math> иногда называют Шаблон:Не переведено 5Шаблон:Sfn.
Представление в виде тора также облегчает понимание точек кручения эллиптической кривой: если решётка Λ порождена фундаментальными периодами <math>\omega_1</math> и <math>\omega_2</math>, то точки <math>n</math>-кручения — это классы эквивалентности точек
- <math>\frac{a}{n} \omega_1 + \frac{b}{n} \omega_2,</math>
где <math>a</math> и <math>b</math> — целые числа от <math>0</math> до <math>n - 1</math>.
Каждая эллиптическая кривая над комплексными числами имеет девять точек перегиба. На каждой прямой, проходящей через две точки перегиба, лежит третья точка перегиба; 9 точек и 12 прямых, построенных таким образом, образуют конфигурацию Гессе.
Эллиптические кривые над полем рациональных чисел
Если коэффициенты уравнения эллиптической кривой <math>E</math> рациональны, то можно рассматривать множество рациональных точек на такой кривой (включая <math>O</math>). Это множество образует подгруппу группы действительных точек (включая <math>O</math>) на кривой <math>E</math> с таким же групповым законом сложения точек на кривой. Это можно показать следующим образом: рассмотрим алгебраическую формулу получения координаты суммы двух точек <math>P</math> и <math>Q</math>, лежащих на кривой <math>E</math>. Если эти точки и коэффициенты уравнения кривой рациональны, то координаты точки <math>R = P + Q</math> тоже будут рациональны, так как <math>x_R</math> и <math>y_Q</math> являются рациональными функциями от коэффициентов кривой <math>E</math> координат точек <math>P</math> и <math>Q</math>Шаблон:Sfn.
Порядком точки <math>P</math> на кривой <math>E</math> называется наименьшее натуральное <math>k</math> такое, что <math>kP = O</math>.
Для эллиптических кривых над полем рациональных чисел справедлива Шаблон:Нп5: на эллиптической кривой <math>E</math> существует такое конечное множество рациональных точек бесконечного порядка <math>P_1, P_2, \dots, P_n</math>, что любая точка на эллиптической кривой представляется в виде
- <math>P = a_1 P_1 + a_2 P_2 + \dots + a_n P_n + Q,</math>
где <math>a_1, \dots, a_n </math> — целые числа, однозначно определённые для точки <math>P</math>, а <math>Q</math> — точка кручения, являющаяся точкой конечного порядкаШаблон:Sfn. Другими словами, теорема гласит, что если поле <math>K</math> — поле рациональных чисел, то группа <math>K</math>-рациональных точек — конечнопорождённая. Это означает, что группа может быть представлена как прямая сумма свободной абелевой группы и конечной подгруппы крученияШаблон:Sfn.
Рангом эллиптической кривой <math>E</math> называется минимальное число рациональных точек бесконечного порядка из теоремы Морделла. Нет общего алгоритма для вычисления ранга свободной подгруппы и, соответственно, ранга эллиптической кривой. Формула для вычисления ранга даётся в гипотезе Бёрча — Свиннертон-Дайера.
На 2021 год эллиптическая кривая с максимальным точно известным рангом описывается следующим уравнением:
- <math>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 + {}</math>
- <math>{} + 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.</math>
Её ранг равен 20, она была найдена Ноамом Элкисом и Зевом Клагсберном в 2020 году[3]. Про следующую кривую, найденную Элкисом в 2006 году и описываемую уравнением
- <math>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>{} + 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, однако точный ранг этой кривой неизвестен[4]. В 2016 году было опубликовано доказательство того, что ранг этой кривой равен в точности 28, если верна обобщённая гипотеза Римана[5].
Эллиптические кривые над конечными полями
Эллиптическую кривую <math>E</math> можно определить над конечным полем <math>\mathbb{F}_q</math>, где <math>q = p^r</math>, а <math>p</math> — простое.
Точное число точек эллиптической кривой <math>E</math> над полем <math>\mathbb{F}_q</math> вычислить достаточно трудно, однако теорема Хассе об эллиптических кривых даёт следующую оценкуШаблон:Sfn:
- <math>\big| \#E(\mathbb{F}_q) - q - 1 \big| \leqslant 2 \sqrt{q}.</math>
Этот факт можно истолковать и доказать с помощью общей теории; см. Локальная дзета-функция, Шаблон:Не переведено 5.
Число точек на конкретной кривой может быть вычислено с помощью алгоритма Шуфа.
Приложения
Эллиптические кривые над конечными полями используются в некоторых криптографических приложениях для факторизации и тестирования простоты чисел. Обычно основная идея, заложенная в этих приложениях, заключается в том, что известный алгоритм, используемый для конкретных конечных групп, переписывается для использования групп рациональных точек эллиптических кривых.
В теории чисел эллиптические кривые были, в частности, использованы Эндрю Джоном Уайлсом (совместно с Ричардом Тейлором) в доказательстве великой теоремы Ферма.
В криптографии они образуют самостоятельный раздел эллиптической криптографии, посвящённый изучению криптосистем на базе эллиптических кривых. В частности, на эллиптических кривых основаны российские стандарты ГОСТ Р 34.10-2001 и сменивший его ГОСТ Р 34.10-2012, описывающие алгоритмы формирования и проверки электронной цифровой подписи.
Примечания
Литература
- Клеменс, Г. Мозаика теории комплексных кривых. — М.: Мир, 1984.
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
Ссылки
- ↑ Шаблон:Статья
- ↑ Шаблон:Книга
- ↑ Шаблон:Cite web
- ↑ 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Шаблон:Nbsp28 subject only to GRH. arXiv preprint arXiv:1606.07178 (2016).
