Эллиптические кривые

Эллиптическая кривая — это невырожденная алгебраическая кривая рода 1, задаваемая уравнением вида \( y^2 = x^3 + ax + b \) (в форме Вейерштрасса) над некоторым полем, при условии, что дискриминант кубического многочлена не равен нулю (то есть кривая не имеет особых точек — каспов или самопересечений). Эллиптические кривые являются одним из центральных объектов изучения в алгебраической геометрии, теории чисел и криптографии.

История

Происхождение и античность

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

Развитие в XVIII–XIX веках

В XVIII веке Леонард Эйлер и Адриен Мари Лежандр систематически изучали эллиптические интегралы и их свойства. В начале XIX века Нильс Хенрик Абель и Карл Густав Якоб Якоби независимо друг от друга открыли, что обратные функции к эллиптическим интегралам — эллиптические функции — являются двоякопериодическими мероморфными функциями на комплексной плоскости. Это привело к пониманию, что эллиптические кривые над комплексными числами можно отождествить с комплексными торами — фактор-пространствами \( \mathbb{C} / \Lambda \), где \( \Lambda \) — решётка в комплексной плоскости.

Модулярные формы и теорема о модулярности

В XX веке эллиптические кривые стали ключевым объектом в теории чисел. В 1950-х годах Горо Шимура и Ютака Танияма выдвинули гипотезу о том, что каждая эллиптическая кривая над полем рациональных чисел является модулярной, то есть связана с модулярными формами. Эта гипотеза, известная как гипотеза Таниямы — Шимуры, была частично доказана Эндрю Уайлсом в 1994 году для полустабильных эллиптических кривых, что позволило доказать Великую теорему Ферма. Полное доказательство гипотезы было завершено в 2001 году группой математиков (Кристоф Брей, Брайан Конрад, Фред Даймонд, Ричард Тейлор). Теперь это утверждение называется теоремой о модулярности.

Математическое определение

Форма Вейерштрасса

Эллиптическая кривая \( E \) над полем \( K \) (характеристика которого не равна 2 или 3) задаётся уравнением: \[ y^2 = x^3 + ax + b, \] где \( a, b \in K \), и дискриминант \( \Delta = -16(4a^3 + 27b^2) \neq 0 \). Условие \( \Delta \neq 0 \) гарантирует, что кривая не имеет особых точек.

Групповая структура

Одним из ключевых свойств эллиптических кривых является то, что множество точек на кривой вместе с бесконечно удалённой точкой \( O \) образует абелеву группу относительно операции сложения точек. Геометрически сложение двух точек \( P \) и \( Q \) на кривой определяется следующим образом: проводится прямая через \( P \) и \( Q \); она пересекает кривую в третьей точке \( R \); затем отражаем \( R \) относительно оси абсцисс — полученная точка \( -R \) и есть сумма \( P + Q \). Бесконечно удалённая точка \( O \) играет роль нулевого элемента.

Инвариант \( j \)

Для эллиптической кривой в форме Вейерштрасса определяется \( j \)-инвариант: \[ j = 1728 \frac{4a^3}{4a^3 + 27b^2}. \] Две эллиптические кривые над алгебраически замкнутым полем изоморфны тогда и только тогда, когда их \( j \)-инварианты совпадают.

Классификация

По полю определения

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

• Над полем комплексных чисел \( \mathbb{C} \) — изоморфны комплексным торам \( \mathbb{C} / \Lambda \), где \( \Lambda \) — решётка.
• Над полем рациональных чисел \( \mathbb{Q} \) — основной объект изучения в теории чисел. Множество рациональных точек \( E(\mathbb{Q}) \) по теореме Морделла — Вейля является конечно порождённой абелевой группой.
• Над конечными полями \( \mathbb{F}_q \) — используются в криптографии, так как число точек на такой кривой конечно и вычисляется с помощью алгоритма Шуфа.
• Над полем вещественных чисел \( \mathbb{R} \) — кривая может иметь одну или две связные компоненты в зависимости от числа вещественных корней кубического многочлена.

По рангу

Ранг эллиптической кривой — это размерность свободной части группы \( E(\mathbb{Q}) \). Кривые с нулевым рангом имеют конечное число рациональных точек, с положительным рангом — бесконечно много. Проблема определения ранга произвольной эллиптической кривой остаётся открытой.

Применение

Криптография

Эллиптические кривые широко используются в криптографии с открытым ключом. Основой является задача дискретного логарифмирования на эллиптической кривой (ECDSA — алгоритм цифровой подписи на эллиптических кривых). Преимущество эллиптической криптографии перед классическими системами (например, RSA) — меньшая длина ключа при том же уровне безопасности. Например, 256-битный ключ на эллиптической кривой обеспечивает сопоставимую стойкость с 3072-битным ключом RSA. В России стандарт ГОСТ Р 34.10-2012 определяет алгоритмы электронной подписи на эллиптических кривых.

Теория чисел

Эллиптические кривые играют центральную роль в доказательстве Великой теоремы Ферма (Эндрю Уайлс, 1994). Они также используются в гипотезе Берча — Свиннертон-Дайера, которая является одной из семи «задач тысячелетия» (за её решение Институт Клэя предлагает приз в 1 миллион долларов). Эта гипотеза связывает ранг эллиптической кривой с поведением её L-функции в точке \( s=1 \).

Факторизация целых чисел

Метод эллиптических кривых (ECM), разработанный Хендриком Ленстрой в 1985 году, используется для факторизации больших составных чисел. Он особенно эффективен для нахождения делителей среднего размера.

Примеры

Кривая \( y^2 = x^3 - x \)

Эта кривая над полем рациональных чисел имеет ранг 1. Её рациональные точки включают, например, \( (0,0) \), \( (1,0) \), \( (-1,0) \), а также бесконечно много других, порождённых точкой \( (2, \sqrt{6}) \) (координата \( y \) не рациональна, но после сложения с другими точками даёт рациональные).

Кривая \( y^2 = x^3 + 1 \)

Эта кривая имеет ранг 0. Её рациональные точки — это \( (-1,0) \), \( (0,1) \), \( (0,-1) \), \( (2,3) \), \( (2,-3) \) и бесконечно удалённая точка. Всего их конечное число.

Интересные факты

• Эллиптические кривые используются в алгоритме биткойна для генерации цифровых подписей (ECDSA). Кривая secp256k1 является стандартом для криптовалют.
• В 1994 году Эндрю Уайлс, доказывая Великую теорему Ферма, использовал эллиптические кривые, связанные с гипотетическим контрпримером к теореме (так называемые кривые Фрея). Это привело к полному доказательству теоремы, которая оставалась нерешённой более 350 лет.
• Существует гипотеза о том, что любая эллиптическая кривая над \( \mathbb{Q} \) имеет конечное число точек с целыми координатами (теорема Зигеля, доказана в 1929 году). Однако для рациональных точек это неверно — их может быть бесконечно много при положительном ранге.

Критика и ограничения

Несмотря на широкое применение, эллиптическая криптография имеет уязвимости. В 2013 году Эдвард Сноуден раскрыл информацию о возможном внедрении ослабленных алгоритмов (backdoors) в стандарты NIST, что привело к критике использования некоторых кривых, таких как P-256. В ответ на это сообщество разработало альтернативные кривые, например Curve25519, которые считаются более устойчивыми к атакам. Также существует потенциальная угроза со стороны квантовых компьютеров: алгоритм Шора позволяет эффективно решать задачу дискретного логарифмирования на эллиптических кривых, что может сделать современную криптографию на эллиптических кривых небезопасной в будущем.

Источники

• Сильверман Дж. «Арифметика эллиптических кривых». — М.: МЦНМО, 2009.
• Коблиц Н. «Курс теории чисел и криптографии». — М.: Наука, 2001.
• Уайлс Э. «Modular elliptic curves and Fermat's last theorem». — Annals of Mathematics, 1995.
• Ленстра Х. «Factoring integers with elliptic curves». — Annals of Mathematics, 1987.
• ГОСТ Р 34.10-2012. «Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи».