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

В математике эллиптической кривой называется плоская кривая, определённая уравнением вида

y² = x³ + a x + b.

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


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

Эллиптическая кривая вовсе не то же самое, что эллипс: см. эллиптический интеграл о происхождении термина.

Содержание

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

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

Эллиптическая кривая — плоская кривая, определённая уравнением вида

y2 = x3 + ax + b,

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

Например, на следующем чертеже показаны эллиптические кривые, определённые уравнениями y2 = x3x and y2 = x3x + 1.

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

Δ = − 16(4a3 + 27b2)

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

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

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

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

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

Описанная группа может быть описана и алгебраически. Пусть дана кривая y² = x³ − pxq над полем K (чья характеристика не равна ни 2, ни 3), и точки P = (xP, yP) и Q = (xQ, yQ) на кривой, допустим, что xPxQ. Пусть s = (yPyQ)/(xPxQ); так как K — поле, то s чётко определено. Тогда мы можем определить R = P + Q = (xR, yR) следующим образом:

xR = s2xPxQ,
yR = − yP + s(xPxR).

Если xP = xQ, то у нас два варианта: если yP = −yQ, то сумма определена как 0; значит, обратную точку к любой точке на кривой можно найти, отразив её по оси Ox. Если yP = yQ ≠ 0, то R = P + P = 2P = (xR, yR) определяется так:

s = {(3{x_P}^2 - p)}/{(2y_P)},
xR = s2 − 2xP,
yR = − yP + s(xPxR).

Если yP = yQ = 0, то P + P = 0.

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

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

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

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

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

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

Классы изоморфизма можно рассмотреть более простым способом. Константы g2 и g3, называемые модулярными инвариантами, единственным образом определены структурой тора. Впрочем, комплексные числа являются полем разложения для многочленов, а значит, эллиптические кривые можно записать как

y2 = x(x − 1)(x − λ).

Можно показать, что

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² = x³ − pxq,

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

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

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

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

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

Точное число рациональных точек эллиптической кривой E над конечным полем Fp достаточно трудно вычислить, но теорема Хассе об эллиптических кривых утверждает, что

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

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

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

Алгоритмы, использующие эллиптические кривые

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

  • Криптография с использованием эллиптических кривых
  • DSA с эллиптическими кривыми
  • Факторизация c помощью эллиптических кривых Ленстры
  • Доказательство простоты с помощью эллиптических кривых.

Внешние ссылки


 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home