Группа точек

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

Исторический контекст

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

В 1920-х годах Андре Вейль и другие математики систематизировали алгебраическую геометрию, введя строгие определения для абелевых многообразий. Эллиптическая кривая, как частный случай абелева многообразия размерности 1, стала центральным объектом. В 1940-х годах Вейль доказал гипотезу о конечности числа образующих группы рациональных точек на эллиптической кривой (теорема Морделла — Вейля), что стало одним из ключевых результатов в этой области.

В конце XX века, с развитием криптографии с открытым ключом, группа точек эллиптической кривой приобрела огромное практическое значение. В 1985 году Нил Коблиц и Виктор Миллер независимо предложили использовать её для построения криптосистем, что привело к созданию криптографии на эллиптических кривых (ECC).

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

Группа точек на эллиптической кривой

Пусть дана эллиптическая кривая \( E \) над полем \( K \), заданная уравнением Вейерштрасса: \[ y^2 = x^3 + ax + b \] где \( a, b \in K \) и дискриминант \( \Delta = -16(4a^3 + 27b^2) \neq 0 \). Множество точек на этой кривой, включая бесконечно удалённую точку \( O \), обозначается \( E(K) \).

На этом множестве вводится операция сложения:

1. Точка на бесконечности \( O \) является нейтральным элементом: \( P + O = O + P = P \).
2. Для двух точек \( P = (x_1, y_1) \) и \( Q = (x_2, y_2) \) на кривой, их сумма \( R = P + Q \) определяется геометрически: проводится прямая через \( P \) и \( Q \); она пересекает кривую в третьей точке \( S \); затем \( R \) получается отражением \( S \) относительно оси \( x \) (то есть \( R = (x_S, -y_S) \)).
3. Если \( P = Q \), то прямая заменяется касательной в этой точке.
4. Если \( P \) и \( Q \) симметричны относительно оси \( x \) (то есть \( y_1 = -y_2 \)), то \( P + Q = O \).

Эта операция удовлетворяет всем аксиомам группы: она ассоциативна, коммутативна (то есть группа является абелевой), существует нейтральный элемент и обратный элемент (для точки \( P = (x, y) \) обратным будет \( -P = (x, -y) \)).

Группа точек на других многообразиях

Понятие группы точек обобщается на любые абелевы многообразия — проективные алгебраические многообразия, которые сами являются алгебраическими группами. Примеры включают:

• Якобианы кривых — группы точек на многообразии, параметризующем классы дивизоров на кривой.
• Торы — группы точек на алгебраическом торе, например, на мультипликативной группе поля \( K^* \).

Классификация и структура

Конечные и бесконечные группы

В зависимости от поля \( K \), группа точек \( E(K) \) может быть:

• Конечной, если \( K \) — конечное поле (например, \( \mathbb{F}_p \)). В этом случае группа точек имеет вид \( \mathbb{Z}_n \) или \( \mathbb{Z}_{n_1} \times \mathbb{Z}_{n_2} \).
• Бесконечной, если \( K \) — поле рациональных чисел \( \mathbb{Q} \). По теореме Морделла — Вейля, группа \( E(\mathbb{Q}) \) является конечно порождённой абелевой группой:

\[ E(\mathbb{Q}) \cong \mathbb{Z}^r \times T \] где \( r \) — ранг эллиптической кривой, а \( T \) — конечная подгруппа кручения.

Ранг эллиптической кривой

Ранг \( r \) — один из важнейших инвариантов эллиптической кривой. Он может быть равен нулю (кривая имеет только конечное число рациональных точек) или положительным. Нахождение ранга — сложная вычислительная задача. Известны кривые с рангом до 28 (по состоянию на 2020-е годы). Гипотеза Бёрча — Свиннертон-Дайера, одна из проблем тысячелетия, связывает ранг с поведением L-функции кривой.

Подгруппа кручения

Конечная часть \( T \) группы \( E(\mathbb{Q}) \) хорошо изучена. По теореме Мазура (1977), возможные подгруппы кручения для эллиптических кривых над \( \mathbb{Q} \) ограничены: это \( \mathbb{Z}_n \) для \( n = 1, 2, \dots, 10, 12 \) или \( \mathbb{Z}_2 \times \mathbb{Z}_{2n} \) для \( n = 1, 2, 3, 4 \).

Применение

Криптография на эллиптических кривых (ECC)

Группа точек эллиптической кривой над конечным полем используется для построения криптосистем с открытым ключом. Основные преимущества ECC перед RSA — меньшие размеры ключей при сопоставимой стойкости. Например, 256-битный ключ ECC обеспечивает уровень безопасности, эквивалентный 3072-битному ключу RSA.

Основные алгоритмы:

• ECDH (Elliptic Curve Diffie-Hellman) — протокол обмена ключами.
• ECDSA (Elliptic Curve Digital Signature Algorithm) — алгоритм цифровой подписи.
• EdDSA (Edwards-curve Digital Signature Algorithm) — вариант на кривых Эдвардса.

ECC широко применяется в протоколах TLS, в криптовалютах (например, Bitcoin использует кривую secp256k1), в смарт-картах и в системах электронной подписи.

Теория чисел

Группа точек на эллиптической кривой используется для решения задач теории чисел, в том числе:

• Факторизация целых чисел (метод Ленстры с использованием эллиптических кривых).
• Доказательство простоты (тест на простоту с помощью эллиптических кривых, ECPP).
• Поиск рациональных точек на кривых и диофантовых уравнениях.

Алгебраическая геометрия

Группа точек является ключевым объектом при изучении абелевых многообразий, их изогений, модулярных форм и гипотезы Таниямы — Шимуры (доказанной для полустабильных кривых Эндрю Уайлсом в 1994 году, что привело к доказательству Великой теоремы Ферма).

Примеры

Пример 1: Кривая над конечным полем

Рассмотрим эллиптическую кривую \( y^2 = x^3 + x + 1 \) над полем \( \mathbb{F}_5 \) (элементы 0, 1, 2, 3, 4). Точки на кривой:

• \( (0, 1) \), \( (0, 4) \)
• \( (2, 1) \), \( (2, 4) \)
• \( (3, 1) \), \( (3, 4) \)
• \( (4, 2) \), \( (4, 3) \)
• Бесконечно удалённая точка \( O \).

Всего 9 точек. Группа \( E(\mathbb{F}_5) \) изоморфна \( \mathbb{Z}_9 \) (циклическая группа порядка 9).

Пример 2: Кривая над рациональными числами

Кривая \( y^2 = x^3 - 2 \) имеет рациональные точки: \( (3, 5) \), \( (3, -5) \), \( O \). Ранг этой кривой равен 1, подгруппа кручения тривиальна. Группа \( E(\mathbb{Q}) \cong \mathbb{Z} \).

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

• Гипотеза Бёрча — Свиннертон-Дайера — одна из семи «задач тысячелетия» Математического института Клэя. За её доказательство назначен приз в 1 миллион долларов США.
• Кривая secp256k1, используемая в Bitcoin, была выбрана из-за своей эффективности и отсутствия известных уязвимостей. Её группа точек имеет порядок, близкий к \( 2^{256} \).
• Теорема Морделла — Вейля обобщается на абелевы многообразия любой размерности, но доказательство для эллиптических кривых было получено раньше.
• Криптография на эллиптических кривых признана Национальным институтом стандартов и технологий США (NIST) и рекомендована для использования в государственных системах.

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

• Сложность реализации: корректная реализация операций в группе точек требует высокой точности и учёта особых случаев (например, деление на ноль при сложении совпадающих точек).
• Уязвимости: некоторые кривые (например, с нестандартными параметрами) могут содержать скрытые уязвимости, такие как малая подгруппа или возможность атаки с помощью квантового компьютера (алгоритм Шора теоретически ломает ECC, но квантовые компьютеры достаточной мощности пока не созданы).
• Сложность вычисления ранга: для многих кривых ранг неизвестен, что ограничивает применимость в некоторых теоретических задачах.

Источники

1. Silverman, J. H. The Arithmetic of Elliptic Curves. Springer, 2009.
2. Koblitz, N. A Course in Number Theory and Cryptography. Springer, 1994.
3. Washington, L. C. Elliptic Curves: Number Theory and Cryptography. CRC Press, 2008.
4. Mazur, B. Modular Curves and the Eisenstein Ideal. Publications Mathématiques de l'IHÉS, 1977.
5. Weil, A. Sur les courbes algébriques et les variétés qui s'en déduisent. Hermann, 1948.