Кольца: сложение + умножение

Комплексные числа изобрели потому, что x² = -1 не имело решений в R. Но это не магия - это факторкольцо: R[x]/(x²+1). Кольцо буквально создаёт новые числа из старых, добавляя одно уравнение. AES-256, RSA, CRYSTALS-Kyber (постквантовый стандарт NIST 2024) - все работают в кольцах. Абстрактная алгебра охраняет интернет.

• **AES-256**: каждая операция шифрования - умножение в GF(2⁸) = F₂[x]/(x⁸+x⁴+x³+x+1). Кольцо многочленов над GF(2) с 256 элементами - именно здесь живёт каждый байт AES.
• **RSA / Диффи-Хеллман / DSA**: кольцо вычетов Z/nZ - базовая структура. Безопасность RSA держится на том, что в Z/nZ трудно найти корень многочлена.
• **CRYSTALS-Kyber (постквантовая криптография)**: работает в кольце Z[x]/(xⁿ+1). NTT - аналог FFT в этом кольце - ускоряет умножение многочленов с O(n²) до O(n log n).
• **Гомоморфное шифрование TFHE**: вычисления прямо над зашифрованными данными - в кольце Z[x]/(xⁿ+1). Основа cloud computing без утечки данных.

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

• Гомоморфизмы и изоморфизмы

Аксиомы кольца: две операции

**Группа** - одна операция. **Кольцо** - две, и вторая дистрибутивна над первой. Это крошечное добавление меняет всё: появляются делители нуля, нильпотентные элементы, идеалы - объекты, которых просто нет в мире групп. Формально: **кольцо** - множество R с операциями (+, ×), где (R, +) - абелева группа, (R, ×) - ассоциативная полугруппа, и умножение дистрибутивно над сложением с обеих сторон.

**Три степени свободы, которых нет в группах:** делители нуля (2×3=0 в Z/6Z), нильпотентные элементы (a с a^n=0), идеалы (подструктуры, поглощающие умножение). Именно из идеалов строятся факторкольца - и именно так R[x]/(x²+1) становится полем комплексных чисел.

Кольца вокруг нас: от Z/nZ до GF(2⁸)

Кольца - не абстракция ради абстракции. Z/nZ лежит в основе RSA и Диффи-Хеллмана. GF(2⁸) = F₂[x]/(x⁸+x⁴+x³+x+1) - это поле, в котором работает каждая операция AES-256. Кольцо Z[x]/(xⁿ+1) используется в CRYSTALS-Kyber - постквантовом стандарте NIST 2024 года. Разберём иерархию.

**Делители нуля разрушают привычную алгебру.** В Z можно сократить: если 2a = 2b, то a = b. В Z₆ это неверно: 2×1 = 2 и 2×4 = 8 = 2 (mod 6), но 1 ≠ 4. В криптографии это критично: Cloudflare однажды нашла баг в реализации умножения в GF(2⁸), который полностью ломал AES. Перед сокращением - убедиться, что элемент не делитель нуля.

Идеалы и факторкольца: откуда берутся комплексные числа

**Идеал** I кольца R - это подгруппа (R, +), которая поглощает умножение: для любых r ∈ R и a ∈ I имеем ra ∈ I и ar ∈ I. Идеалы - аналог нормальных подгрупп для колец. По ним строятся факторкольца R/I. И это не просто конструкция - это механизм, которым математика буквально создаёт новые числа из старых.

**C = R[x]/(x²+1) - это не метафора.** Добавляем одно уравнение: x² = -1. Это убивает все многочлены степени выше 1 (делим с остатком), и остаётся ровно то, что нужно: a + bx с i = x. NTT (Number Theoretic Transform) - та же идея в кольце Z[x]/(xⁿ+1). На нём работает CRYSTALS-Kyber, постквантовый стандарт NIST. Факторкольцо как инструмент построения криптографии.

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

• Кольцо: (R, +) - абелева группа + (R, ×) - ассоциативная операция + дистрибутивность
• Коммутативное кольцо: ab = ba. Кольцо с единицей: существует 1 такое что a×1 = a
• Делители нуля: ненулевые a, b с ab = 0. Ломают сокращение. В AES ошибка здесь = cryptographic break
• Идеал I: подгруппа по +, поглощающая умножение. По идеалам строятся факторкольца R/I
• C = R[x]/(x²+1): комплексные числа как факторкольцо. x² = -1 не магия, а следствие структуры
• GF(2⁸), Z/nZ, Z[x]/(xⁿ+1) - три кольца, на которых держится современная криптография

Что дальше

Поля - особые кольца, где у каждого ненулевого элемента есть мультипликативный обратный. Они дают рациональные, вещественные, комплексные числа и конечные поля GF(pⁿ).

• Поля и их применения — Поле = коммутативное кольцо с единицей без делителей нуля, где каждый ненулевой обратим
• Многочлены — R[x] - главный источник примеров колец и полей через факторизацию

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

• Является ли Q[x]/(x²-2) полем? Почему? (Подсказка: является ли x²-2 неприводимым над Q?)
• NTT (Number Theoretic Transform) - это FFT в кольце Z[x]/(xⁿ+1). Какое свойство кольца позволяет заменить комплексные корни из единицы на целочисленные?
• Почему Z/nZ является полем тогда и только тогда, когда n - простое число? Как это связано с тем, что у простых p нет делителей нуля в Z/pZ?

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

• aa-03-homomorphisms — Гомоморфизмы - язык для понимания факторколец
• aa-05-fields — Поле = кольцо без делителей нуля с обратными
• aa-09-polynomials — Кольца многочленов - главный источник примеров
• aa-21-algebra-crypto — RSA, AES, постквантовая криптография через кольца
• nt-01 — Z/nZ - связующее звено между числами и кольцами
• crypto-04-algebraic-structures