Алгебраическая теория чисел (обзор)

В 2022 году NIST стандартизировал CRYSTALS-Kyber и CRYSTALS-Dilithium - первые post-quantum стандарты шифрования. Оба работают в кольце ℤq[x]/(xⁿ+1). Это кольцо целых в числовом поле - объект, придуманный Куммером и Дедекиндом в XIX веке для решения теорем Ферма. Алгебраическая теория чисел 150-летней давности защищает данные пользователей от будущих квантовых компьютеров.

• **CRYSTALS-Kyber (NIST PQC):** KEM на основе Module-LWE в кольце R_q = Z_q[x]/(x^256+1)
• **CRYSTALS-Dilithium:** подпись на основе Module-LWE/SIS; то же кольцо, другие параметры
• **NTRU:** первый решёточный криптостандарт (1996); работает в кольце Z[x]/(x^n−1)

Предварительные знания

• Diophantine Equations

Алгебраические целые и числовые поля

Что если расширить целые числа ℤ, добавив корни уравнений? Число √2 - корень x²−2=0 - алгебраическое, но иррациональное. Кольцо ℤ[√2] = {a + b√2 : a,b ∈ ℤ} - первый пример кольца алгебраических целых. В нём есть сложение, умножение и свои «простые».

**Алгебраическое целое:** число α, являющееся корнем унитарного многочлена с целыми коэффициентами. **Числовое поле ℚ(√d):** {a + b√d : a,b ∈ ℚ} для несквадратного d. **Кольцо целых 𝒪_K:** - d ≡ 2,3 (mod 4): 𝒪_K = ℤ[√d] = {a+b√d : a,b ∈ ℤ} - d ≡ 1 (mod 4): 𝒪_K = ℤ[(1+√d)/2] **Норма:** N(a+b√d) = a² − d·b² **Примеры:** ℤ[i] (гауссовы целые, d=−1), ℤ[√2], ℤ[√−5]

Норма мультипликативна: N(αβ) = N(α)·N(β). Это ключевое свойство: если α - гауссово простое, то N(α) = p или p² для обычного простого p. Норма даёт мост между ℤ[i] и ℤ.

ℤ[i] и уникальность факторизации

В ℤ[i] сохраняется фундаментальная теорема арифметики: каждый элемент единственным образом (с точностью до единиц {1,−1,i,−i}) разлагается на гауссовы простые. Не все кольца так устроены - ℤ[√−5] теряет уникальность.

**Гауссовы единицы:** {1, −1, i, −i} - обратимые элементы ℤ[i]. **Уникальная факторизация (UFD):** каждый ненулевой не-единичный элемент = ε · π₁ · π₂ · ... единственным образом (ε - единица, πᵢ - гауссовы простые). **Потеря уникальности в ℤ[√−5]:** 6 = 2 · 3 = (1+√−5)(1−√−5) Оба разложения в ℤ[√−5] не сводимы дальше! **Числа Кумера:** для восстановления уникальности Кумер (1847) ввёл «идеальные числа» - прообраз современных идеалов.

Теорема Ферма о двух квадратах: нечётное простое p представимо как сумма двух квадратов p = a² + b² тогда и только тогда, когда p ≡ 1 (mod 4). Доказательство элегантно использует гауссовы целые и является одним из первых успехов алгебраической теории чисел.

Домены Дедекинда и идеальная факторизация

В ℤ[√−5] уникальность факторизации нарушается: 6 = 2·3 = (1+√−5)(1−√−5). Дедекинд (1871) восстановил уникальность, введя идеалы: не элементы, а подмножества кольца. В терминах идеалов факторизация снова единственна.

**Идеал I ⊂ R:** подмножество кольца, замкнутое по сложению и умножению на элементы кольца. **Главный идеал (α):** I = {α·r : r ∈ R} **Основная теорема доменов Дедекинда:** В кольце целых числового поля каждый идеал единственным образом раскладывается в произведение простых идеалов: I = P₁^{e₁} · P₂^{e₂} · ... · Pₖ^{eₖ} **Пример в ℤ[√−5]:** (6) = P₁·P₂·P₃·P₄ - четыре простых идеала Восстанавливает «уникальность» через идеалы

Для понимания современной криптографии на решётках (NTRU, Kyber) важно знать: их безопасность основана на жёсткости задач в кольцах вида ℤ[x]/(xⁿ+1) - это кольца целых в специальных числовых полях. Идеалы таких колец определяют структуру атак.

Связь с решёточной криптографией

Кольца целых числовых полей - не абстракция. Стандарты post-quantum криптографии CRYSTALS-Kyber и CRYSTALS-Dilithium работают в кольце Rq = ℤq[x]/(xⁿ+1), которое является кольцом целых в циклотомическом поле ℚ(ζ₂ₙ). Безопасность - жёсткость задачи Module-LWE в этом кольце.

**Решёточная криптография - фундамент:** **Задача SVP (Shortest Vector Problem):** найти кратчайший ненулевой вектор в решётке. **Задача LWE (Learning With Errors):** различить A·s + e от случайного, где e - малый шум. **Задача Ring-LWE:** LWE в кольце R = ℤ[x]/(xⁿ+1). **CRYSTALS-Kyber (NIST 2022):** KEM на основе Module-LWE в R_q. **CRYSTALS-Dilithium (NIST 2022):** подпись на основе Module-LWE/SIS. **Почему кольцо R:** умножение полиномов быстрее матричного; стойкость сохраняется.

Алгебраическая теория чисел - не только история. Кольца вида ℤ[x]/(f(x)) при правильном выборе f(x) дают идеальную структуру для post-quantum криптографии: умножение реализуется через NTT за O(n log n), а задача Ring-LWE, насколько известно, стойка к квантовым атакам.

Ключевые идеи

• **Числовые поля:** ℚ(√d) содержит алгебраические целые; кольцо целых 𝒪_K обобщает ℤ
• **ℤ[i] - UFD:** гауссовы целые допускают уникальную факторизацию; простые p ≡ 1 (mod 4) расщепляются
• **ℤ[√−5] - не UFD:** 6 = 2·3 = (1+√-5)(1-√-5); Дедекинд восстановил уникальность через идеалы
• **Post-quantum:** Ring-LWE в ℤq[x]/(xⁿ+1) - основа Kyber и Dilithium (NIST 2022)

Связанные темы

Алгебраическая теория чисел - мост между классической математикой и современной криптографией:

• Диофантовы уравнения — Пифагоровы тройки и уравнение Пелля - первые задачи, решаемые методами числовых полей
• Post-Quantum Cryptography — Kyber и Dilithium строятся на Ring-LWE в кольцах целых циклотомических полей
• Аналитическая теория чисел — L-функции и дзета-функция Дедекинда обобщают дзета Римана на числовые поля

Вопросы для размышления

• Что значит «идеальное разложение восстанавливает уникальность» в ℤ[√−5]? Можно ли конкретно показать, что идеальное разложение числа 6 единственно?
• Норма N(a+b√d) = a²−db² мультипликативна. Как это используется для доказательства того, что элемент является простым в кольце целых?
• Почему для Ring-LWE нужен именно xⁿ+1 (а не xⁿ−1 или другой многочлен)? Какие алгебраические свойства обеспечивает это кольцо?

Связанные уроки

• aa-05-fields