Эллиптическая кривая | это... Что такое Эллиптическая кривая? (original) (raw)

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

Эллипти́ческая крива́я над полем 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. Эллиптические кривые также применяются в некоторых алгоритмах факторизации (например, Алгоритм Ленстры) и тестирования простоты чисел.

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

Содержание

1 Каноническая форма
2 Эллиптические кривые над действительными числами
3 Групповой закон
4 Эллиптические кривые над полем комплексных чисел
5 Эллиптические кривые над произвольным полем
6 Связь с теорией чисел
7 Приложения
8 Список литературы
9 См. также
10 Ссылки

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

Если характеристика поля 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; значит, обратную точку к любой точке на кривой можно найти, отразив её по оси . Если $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$ умножением на ненулевое комплексное число , то соответствующие кривые изоморфны. Классы изоморфизма эллиптических кривых определены 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 может быть представлена в виде тора.

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

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

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

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

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

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

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

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

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

Точное число рациональных точек эллиптической кривой над конечным полем $\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

Кривые
Определения	Аналитическая • Жордана • Канторова • Урысона • Овал • Спрямляемая Радиус кривизны
Преобразованные	Эволюта • Эвольвента • Подера • Антиподера • Параллельная • Дуальная • Каустика
Неплоские	Винтовая линия • Линия откоса • Локсодрома • Ортодромия • Губка
Плоские алгебраические
Конические сечения	Гипербола • Парабола • Эллипс (Окружность)
3-й порядок	Эллиптические: Эллиптическая кривая • Функции Якоби • Интеграл • Функции Другие: Верзьера Аньези • Декартов лист • Кубика • Полукубическая парабола • Строфоида • Циссоида Диокла
Лемнискаты	Бернулли (Овал Кассини) • Бута • Жероно
Аппроксимационные	Сплайн (B-сплайн • Кубический • Моносплайн • Эрмита) • Безье
Циклоидальные	Кардиоида • Нефроида • Дельтоида • Астроида • Улитка Паскаля
Плоские трансцендентные
Спирали	Архимедова (Ферма) • Гиперболическая • «Жезл» • Клотоида • Логарифмическая
Циклоидальные	Циклоида • Эпициклоида • Гипоциклоида • Трохоида (Удлинённая + Укороченная циклоида) • Эпитрохоида (Удлинённая + Укороченная эпициклоида • («Роза») • Гипотрохоида • Скорейшего спуска (Брахистохрона, дуга циклоиды)
Другие	Квадратриса • Погони (Трактриса) • Трохоида • Цепная линия (перевёрнутая арочная) • Постоянной ширины • Синусоида
Фрактальные
Простые	Коха • Леви • Минковского • Пеано
Топологические	Салфетка + Ковёр Серпинского • Губка Менгера