Эта статья входит в число добротных статей

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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

y^2+a_1 xy+a_3 y=x^3+a_2 x^2+a_4 x+a_6.

История[править | править вики-текст]

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

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

Каноническая форма[править | править вики-текст]

Если характеристика поля K (\mathrm{char}\, K) не равна 2 или 3, то уравнение с помощью замены координат приводится к канонической форме (форме Вейерштрасса):

y^2=x^3+ax+b.

Если \mathrm{char}\, K=3, то каноническим видом уравнения является вид:

y^2=x^3+a_2 x^2+a_4 x+a_6.

Если \mathrm{char}\, K=2, то уравнение приводится к одному из видов:

y^2+y=x^3+ax+b — суперсингулярные кривые[en]

или

y^2+xy=x^3+ax^2+b — несуперсингулярные кривые[4].

Эллиптические кривые над действительными числами[править | править вики-текст]

Графики кривых y2 = x3x и y2 = x3x + 1

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

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

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

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

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

\Delta = -16(4a^3 + 27b^2)[4]

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

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

Групповой закон[править | править вики-текст]

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

ECClines-2.0.svg

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

Данная группа может быть описана и алгебраически. Пусть дана кривая y^2=x^3+ax+b над полем K (характеристика которого не равна ни 2, ни 3), и точки P=(x_P,y_P) и Q=(x_Q,y_Q) на кривой, допустим, что x_P\ne x_Q. Пусть \textstyle 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) определяется так:

\textstyle 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[7].

Точка 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[8].

Эллиптические кривые над полем комплексных чисел[править | править вики-текст]

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

\wp'(z)^2 = 4\wp(z)^3 -g_2\wp(z) - g_3,

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

z\to (1,\wp(z), \wp'(z)).

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

Классы изоморфизма можно рассмотреть более простым образом. Константы 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),

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

\Delta = g_2^3-27g_3^2 = \lambda^2(\lambda-1)^2.

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

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

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

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

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

P = a_1 P_1 + a_2 P_2 + ... + a_n P_n + Q,

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

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

y2 + xy + y = x3x2 + 31368015812338065133318565292206590792820353345x + 302038802698566087335643188429543498624522041683

Её ранг равен 19, она была найдена Ноамом Элкисом[en] в 2009 году[13].

Эллиптические кривые над конечными полями[править | править вики-текст]

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

Точное число точек эллиптической кривой E над конечным полем \mathbb{F}_q достаточно трудно вычислить, но теорема Хассе об эллиптических кривых утверждает, что:

 \left| \sharp E( \mathbb{F}_q ) - q - 1 \right| < 2 \sqrt{q} [14].

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

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

Приложения[править | править вики-текст]

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

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

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

Примечания[править | править вики-текст]

  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.
  4. 1 2 Silverman, 2009, p. 42—43.
  5. Коблиц, 2001, с. 192.
  6. Острик, 2001, с. 21—24.
  7. Коблиц, 2001, с. 188—200.
  8. Острик, 2001, с. 24.
  9. Коблиц, 2000, с. 33—37.
  10. Silverman, 2009, p. 20.
  11. Острик, 2001, с. 26.
  12. Коблиц, 2001, с. 195.
  13. Dujella, Andrej. History of elliptic curves rank records (англ.). Andrej Dujella home page.
  14. Silverman, 2009, p. 137—138.

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]