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

Не следует путать с Эллипс.

Эллипти́ческая крива́я над полем K — это множество точек проективной плоскости над K, удовлетворяющих уравнению

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

вместе с точкой на бесконечности.

Эллиптические кривые являются одним из основных объектов изучения в современной теории чисел и криптографии. Например, они были использованы Эндрю Уайлcом (совместно с Ричардом Тейлором) в доказательстве Великой теоремы Ферма. Эллиптическая криптография образует самостоятельный раздел криптографии, посвященный изучению криптосистем на базе эллиптических кривых. В частности, на эллиптических кривых основан российский стандарт цифровой подписи ГОСТ Р 34.10-2001. Эллиптические кривые также применяются в некоторых алгоритмах факторизации (например, Алгоритм Ленстры) и тестирования простоты чисел.

Термин «эллиптическая кривая» происходит от термина «эллиптический интеграл».

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

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

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

Если Char K = 3, то каноническим видом уравнения является вид:

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

А если Char K = 2, то уравнение приводится одному из видов:

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

или

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

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

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

Считаем, что характеристика поля — не 2 и 3. Тогда эллиптическая кривая — плоская кривая, определённая уравнением вида

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

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

Например, на следующем чертеже показаны эллиптические кривые, определённые уравнениями $y^2 = x^3 - x$ и $y^2 = x^3 - x + 1$.

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

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

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

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

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

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

Тогда мы можем ввести групповую операцию «+» на прямой со следующими свойствами: положим, что несобственная точка является нулём группы; и если прямая пересекает данную кривую в точках P, Q и R, то $P+Q+R=0$ в группе. Можно показать, что таким образом кривая превращается в абелеву группу, то есть, в абелево многообразие. Можно также показать, что множество K-рациональных точек (включая несобственную) образует подгруппу этой группы. Для кривой E такая подгруппа обычно обозначается $E(K)$.

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

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

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

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

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

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

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

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

так что дискриминант модуляра равен

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

Здесь λ иногда называют лямбда-функцией модуляра.

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

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

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

Если характеристика поля $K$ не равна 2 или 3, то любая эллиптическая кривая над $K$ может быть записана в виде

$y^2=x^3-px-q$,

где $p$ и $q$ — такие элементы $K$, что многочлен $x^3-px-q$ (правая сторона) не имеет кратных корней. (Если характеристика равна 2 или 3, то необходимо ввести ещё несколько условий.)

Можно взять кривую как множество всех точек $(x;y)$, которые удовлетворяют вышеуказанному уравнению, а $x$ и $y$ одновременно являются элементами алгебраического замыкания поля $K$. Точки кривой, обе координаты которых принадлежат $K$, называются $K$-рациональными точками.

Связь с теорией чисел

Теорема Морделла-Вейля утверждает, что если поле $K$ — поле рациональных чисел (или, вообще, поле чисел), то группа $K$-рациональных точек — конечно порождённая. Это означает, что группа может быть выражена как прямая сумма свободной абелевой группы и конечной подгруппы кручения. Хотя и относительно легко определить подгруппу кручения $E(K)$, но нет общего алгоритма для вычисления ранга свободной подгруппы. Формула для вычисления ранга даётся в гипотезе Бирча и Свиннертона-Дайера.

Недавнее доказательство Великой теоремы Ферма было сделано с помощью доказательства особого случая теоремы Таниямы — Шимуры, относящей эллиптические кривые над рациональными числами к модулярным формам; эта теорема недавно была доказана и в целом.

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

$\left| \sharp E( \mathbb{F}_p ) - p - 1 \right| < 2 \sqrt{p}$.

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

Дальнейшие рассуждения по теме см. в статье Арифметика абелевых многообразий.

Приложения

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

• Эллиптическая криптография
• DSA на эллиптических кривых
• ГОСТ Р 34.10-2001
• Факторизация Ленстры с помощью эллиптических кривых
• Доказательство простоты с помощью эллиптических кривых
• Dual EC DRBG
• ДСТУ 4145-2002
• IBE

Список литературы

• Н. Коблиц Курс теории чисел и криптографии = A Course in Number Theory and Cryptography. — Москва: Научное издательство "ТВП", 2001. — С. 254. — ISBN 5-85484-014-6

• Н. Коблиц Введение в эллиптические кривые и модулярные формы = Introduction to Elliptic Curves and Modular Forms. — Новокузнецк: ИО НФМИ, 2000. — С. 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, 1986. — С. 402. — ISBN 0-387-96203-4

См. также

• Теорема о 9 точках на кубике

Ссылки

• The Mathematical Atlas: 14H52 Elliptic Curves
• Weisstein, Eric W. Elliptic Curves (англ.) на сайте Wolfram MathWorld.
• С. Николенко Эллиптическая криптография // Компьютерра. — 2006. — В. 01.09.06.
• Ю.П. Соловьев Рациональные точки на эллиптических кривых // Соросовский образовательный журнал. — 1997. — № 10. — С. 138-143.
• В. В. Острик, М. А. Цфасман Алгебраическая геометрия и теория чисел: рациональные и эллиптические кривые. — М.: МЦНМО, 2001. — Т. 8. — 48 с. — ISBN 5-900916-71-5