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

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

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

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

Эллиптические кривые являются одним из основных объектов изучения в современной теории чисел и криптографии:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ECClines.svg

Тогда мы можем ввести групповую операцию «+» на прямой со следующими свойствами: положим, что несобственная точка является нулём группы; и если прямая пересекает данную кривую в точках 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 и с выделенной точкой O.

Если характеристика поля 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} .

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

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

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

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

См. также[править | править вики-текст]

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

  • Н. Коблиц Курс теории чисел и криптографии = 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.

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