Поля и их применения

AES-256 шифрует каждый HTTPS-запрос. Каждая операция SubBytes - вычисление обратного в поле GF(2^8). Ошибка в реализации умножения в этом поле = cryptographic break. NIST в 2001 году выбрал AES именно потому, что алгебра GF(2^8) делает его математически анализируемым. Reed-Solomon над GF(2^8) - основа QR-кодов, CD, DVD, спутниковых коммуникаций. Bitcoin ECDSA работает в E(F_p) - группе точек эллиптической кривой над полем простых вычетов. За всем этим - одна структура, которую Галуа написал за ночь до своей гибели в 21 год.

• AES: SubBytes и MixColumns - линейная алгебра над GF(2^8). Весь шифр - арифметика в конечном поле
• Reed-Solomon: коды над GF(2^8) восстанавливают данные QR-кодов (до 30% потерь), CD/DVD, RAID-6, 5G NR
• ECDSA (Bitcoin, TLS 1.3): подписи - элементы поля F_n, где n - порядок группы secp256k1
• CRYSTALS-Kyber (NIST PQC 2024): NTT над Z_3329 - дискретное преобразование в конечном поле

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

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

Что такое поле: аксиомы и примеры

1830. Эваристу Галуа 18 лет. За ночь до дуэли он записывает теорию, которая объяснит, почему уравнение пятой степени нельзя решить в радикалах. Через 170 лет его поля Галуа охраняют каждое TLS-соединение в интернете.

**Поле** - это коммутативное кольцо с единицей, где каждый ненулевой элемент обратим. Два действия, полная обратимость для умножения. Q, R, C - поля. Z - нет: у 2 нет обратного в целых. GF(2) = {0, 1} с 1+1=0 - тоже поле, и это не экзотика: это основа всей двоичной арифметики.

**Характеристика поля**: наименьшее n такое, что 1+1+...+1 (n раз) = 0. Для Q, R, C характеристика 0 - нет такого n. Для GF(p) характеристика p - простое число. Этот инвариант полностью разделяет поля: поле характеристики 0 содержит копию Q, поле характеристики p содержит копию GF(p).

Конечные поля GF(p^n): структура и единственность

Q, R, C - все поля. GF(2) = {0, 1} - тоже поле: 1+1=0. GF(p^n) - конечные поля с ровно p^n элементами. Они существуют для каждого простого p и каждого n - и нигде больше. Эта жёсткость делает их идеальными для криптографии: нельзя подобрать 'похожее' поле с другим числом элементов.

**Теорема Галуа**: конечное поле существует тогда и только тогда, когда его мощность равна p^n для простого p и n >= 1. Такое поле единственно с точностью до изоморфизма. Обозначение: GF(p^n) или F_{p^n}. GF(4) != Z/4Z - потому что 4 = 2^2 не простое.

**Почему GF(2^8) для AES**: операция XOR между байтами - это сложение в GF(256). Умножение - через shift и XOR с модулем. Весь AES математически - это линейная алгебра над GF(256). NIST выбрал именно такую структуру, потому что алгебра конечного поля делает шифр анализируемым - и доказуемо стойким.

Расширения полей и применения: от GF(4) до Kyber

**Расширение поля** F ⊆ K - ситуация, когда K само поле и содержит F как подполе. Башня Q ⊆ R ⊆ C - знакомый пример. Конечные поля строятся через расширение: GF(p^n) = GF(p)[x]/(f(x)), где f - неприводимый многочлен степени n над GF(p). Это буквально факторкольцо многочленов по неприводимому модулю.

**Теорема Абеля-Руффини**: уравнение степени >= 5 в общем виде не решается в радикалах. Доказательство идёт через теорию Галуа: группа Галуа расширения F ⊆ K кодирует симметрии корней. Разрешимость уравнения - разрешимость группы. Для степеней >= 5 группа S_5 неразрешима. За ночь до дуэли Галуа написал это в письме другу.

**IEEE 754 как 'почти-поле'**: числа с плавающей точкой нарушают ассоциативность: (a+b)+c != a+(b+c) из-за ошибок округления. Это не поле. Именно поэтому результаты ML-обучения не воспроизводимы: порядок операций на GPU меняется, суммы приходят в разном порядке. Конечные поля лишены этой проблемы - там ассоциативность точная.

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

• Поле = коммутативное кольцо с единицей, где каждый ненулевой обратим. Деление везде
• Z/nZ - поле тогда и только тогда, когда n простое. Составное n - есть делители нуля
• GF(p^n): конечные поля существуют и единственны для каждого p^n. Нигде больше
• GF(p^n) = GF(p)[x]/(f), где f - неприводимый степени n. Факторкольцо многочленов
• AES, Reed-Solomon, ECDSA, Kyber - все работают в конечных полях Галуа
• IEEE 754 нарушает ассоциативность - не поле. Отсюда невоспроизводимость ML

Что дальше

Факторгруппы и теория Галуа замыкают картину: симметрии расширений полей объясняют разрешимость уравнений.

• Факторгруппы — G/N обобщает факторкольцо; первая теорема изоморфизма
• Теория Галуа: введение — Группа Галуа расширения кодирует симметрии корней уравнения
• Алгебра в криптографии — RSA, ECDSA, AES как конкретные применения конечных полей

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

• Построить GF(4): выписать таблицы сложения и умножения для {0, 1, a, a+1} где a^2 = a+1. Проверить, что каждый ненулевой обратим.
• Почему IEEE 754 не является полем? Найти конкретный контрпример нарушения ассоциативности с маленькими числами.
• Reed-Solomon над GF(2^8) может восстановить 14 повреждённых байт из 255. Почему 255 = 2^8 - 1 - это не совпадение?

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

• aa-04-rings — Поле - специальное коммутативное кольцо с обратными
• aa-06-quotient — Факторкольцо F_p[x]/(f) строит расширения полей
• aa-10-galois-intro — Теория Галуа - симметрии расширений полей
• aa-21-algebra-crypto — RSA, ECDSA, AES - все живут в конечных полях
• aa-22-linear-codes — Reed-Solomon над GF(2^8) - основа QR и DVD
• nt-03 — Z/nZ - прототип конечного поля при простом n
• crypto-04-algebraic-structures
• crypto-26-ecc-math