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

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

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

Эллипти́ческая крива́я над полем 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. Эта задача решается путем замены переменных y = 3y - 1 (по сути, проведением касательной к кривой). Но дальше в изучении эллиптических кривых он продвигаться не стал[3].

В 1670-х годах Ньютон, используя приемы аналитической геометрии, делает попытку классифицировать кривые, называемые кубиками; в ходе исследований Ньютон заметил, что в общем случае прямая может пересекать такую кривую максимум в трех точках, а если прямая — касательная, то точка касания считается за две одинаковые точки. Догадка Ньютона напрямую ведет к формулам сложения точек на эллиптической кривой. В XIX веке эллиптические кривые находят применение в теории эллиптических функций, которые, в свою очередь, тесно связаны с эллиптическими интегралами. Таким образом, исторически термин «эллиптическая кривая» происходит от термина «эллиптический интеграл»[4].

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

Если характеристика поля 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 — несуперсингулярные кривые[5].

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

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

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

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

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

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

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

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

не должен быть равен нулю.

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

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

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

ECClines-2.0.svg

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

Описанная группа может быть описана и алгебраически. Пусть дана кривая 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[8].

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

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

Формулировка эллиптических кривых как вложения тора в комплексную проективную плоскость[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][10].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1. Silverman, 2009, p. 59
  2. Коблиц, 2001, с. 188
  3. Соловьёв, 1997, с. 138—143
  4. Adrian Rice, Ezra Brown Why Ellipses Are Not Elliptic Curves (англ.) // Mathematics Magazine. — 2012. — Vol. 85. — № 3. — P. 163—176.
  5. 1 2 Silverman, 2009, p. 42—43
  6. Коблиц, 2001, с. 192
  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.
  15. Silverman, 2009, p. 137—138

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

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