Теория Галуа

AES (Advanced Encryption Standard) работает в поле Галуа GF(2⁸) - 256 элементов. Каждый байт данных - элемент этого поля, операции S-box - мультипликативные инверсии. Теория Галуа - математика за шифрованием каждого HTTPS-соединения и доказательством того, что формулы для уравнений 5-й степени не существует.

• **AES-128/256:** поле GF(2⁸) используется в ShiftRows, MixColumns, SubBytes - три из четырёх операций AES математически определены в полях Галуа
• **Теорема Абеля-Руффини:** уравнения 5-й и выше степеней не разрешимы в радикалах - доказано через неразрешимость S₅ в 1824 году
• **Коды исправления ошибок:** Reed-Solomon коды (QR-коды, CD, RAID-6) работают над полями Галуа GF(2^m) - теория Галуа за каждым QR-кодом

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

• Алгебра на собеседовании

Расширения полей

AES (Advanced Encryption Standard) работает в поле Галуа GF(2⁸) - 256 элементов. Каждый байт данных - элемент этого поля, операции S-box - мультипликативные инверсии. Поле GF(2⁸) = GF(2)[x]/(x⁸+x⁴+x³+x+1) - расширение GF(2) неприводимым многочленом степени 8. Степень расширения [GF(2⁸):GF(2)] = 8.

На интервью: степень расширения [ℚ(α):ℚ] = степень минимального многочлена α. Для ∛2 это 3, для ∜2 это 4, для √2+√3 это 4 (т.к. [ℚ(√2,√3):ℚ] = 4).

Группа Галуа

Группа Галуа Gal(L/K) - группа всех автоморфизмов поля L, фиксирующих K поточечно. Для ℚ(√2)/ℚ: автоморфизм σ определяется образом √2 → −√2 (другой корень x²−2). Gal(ℚ(√2)/ℚ) = {id, σ} ≅ ℤ/2ℤ. Порядок группы Галуа |Gal(L/K)| = [L:K] для расширений Галуа.

**Теорема о башне:** для K ⊂ F ⊂ L: [L:K] = [L:F]·[F:K]. Это позволяет вычислять степени составных расширений: [ℚ(√2,√3):ℚ] = [ℚ(√2,√3):ℚ(√2)]·[ℚ(√2):ℚ] = 2·2 = 4.

Фундаментальная теорема теории Галуа

Фундаментальная теорема устанавливает взаимооднозначное соответствие: подполя K ⊂ F ⊂ L ↔ подгруппы H ≤ Gal(L/K). Именно это соответствие позволило Галуа доказать неразрешимость общего уравнения пятой степени в радикалах: группа Галуа S₅ не является разрешимой группой.

**Теорема Абеля-Руффини (1824):** общее уравнение степени n ≥ 5 не разрешимо в радикалах. Доказательство: группа Галуа общего уравнения ≅ Sₙ. При n≥5 группа Sₙ не является разрешимой (derived series не обрывается на {e}).

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

• **Расширения полей:** [L:K] = dimₖ L; степень = deg(минимального многочлена); теорема о башне: [L:K] = [L:F]·[F:K]
• **Группа Галуа:** Gal(L/K) - группа автоморфизмов L, фиксирующих K; |Gal(L/K)| = [L:K] для расширений Галуа
• **Фундаментальная теорема:** биекция подполей ↔ подгрупп Gal(L/K); нормальные подгруппы ↔ нормальные расширения
• **Неразрешимость квинтики:** уравнение разрешимо в радикалах ↔ Gal(p) разрешима; S₅ не разрешима → нет формулы для 5-й степени

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

Теория Галуа синтезирует алгебру и теорию групп:

• Теория групп — Группы Галуа - конкретные группы; разрешимые группы определяют разрешимость уравнений
• Теория колец — Кольца многочленов K[x] и фактор-кольца K[x]/(p(x)) - основной способ строить расширения полей

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

• GF(2⁸) = GF(2)[x]/(x⁸+x⁴+x³+x+1). Почему выбран именно этот неприводимый многочлен, а не другой неприводимый многочлен степени 8 над GF(2)?
• Группа Gal(ℚ(∜2,i)/ℚ) ≅ D₄ (диэдральная, порядок 8). Сколько промежуточных подполей существует между ℚ и ℚ(∜2,i)?
• Уравнение x⁵−x−1 = 0 имеет группу Галуа S₅. Как это означает, что его корни нельзя выразить через радикалы, хотя корни вещественные?