Группы

RSA-шифрование, на котором работает HTTPS, основано на теореме Лагранжа для мультипликативной группы ℤ*ₙ. Эквивариантные нейронные сети (E(n)-equivariant, используемые в AlphaFold)-приложение теории групп симметрий к глубокому обучению. Абстрактная алгебра оказывается вполне практичной.

• **RSA-криптография:** безопасность основана на малой теореме Ферма и структуре группы ℤ*ₙ; порядок группы φ(n)-ключ к алгоритму
• **Equivariant NN:** CNN эквивариантны к трансляциям; E(3)-сети-к вращениям/отражениям; AlphaFold использует симметрии SO(3)
• **Перестановочные группы в комбинаторике:** Sₙ считает перестановки; Burnside's lemma считает объекты с симметриями (раскраски, изомерные молекулы)

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

• Eigenvalues and Eigenvectors

Аксиомы и примеры

Группа-это множество G с бинарной операцией ·, удовлетворяющей четырём аксиомам: 1. Замкнутость: a,b ∈ G → a·b ∈ G. 2. Ассоциативность: (a·b)·c = a·(b·c). 3. Единица: существует e ∈ G такое, что e·a = a·e = a для всех a. 4. Обратный: для каждого a ∈ G существует a⁻¹ ∈ G с a·a⁻¹ = e.

**Порядок группы** |G|-число элементов. **Порядок элемента** a-наименьшее k > 0 такое, что aᵏ = e. Для циклической группы ℤₙ порядок элемента k равен n/НОД(n,k).

Подгруппы и смежные классы

Подгруппа H ≤ G-непустое подмножество, замкнутое относительно операции и взятия обратных. Левый смежный класс a по H: aH = {a·h : h ∈ H}. Смежные классы либо совпадают, либо не пересекаются: они разбивают G на непересекающиеся блоки одинакового размера |H|.

**Нормальная подгруппа** N ◁ G: aNa⁻¹ = N для всех a ∈ G. На нормальных подгруппах можно строить **факторгруппу** G/N. Ядро гомоморфизма всегда нормально-это связывает группы и линейную алгебру (ядро линейного отображения).

Теорема Лагранжа и циклические группы

Теорема Лагранжа: если H-подгруппа конечной группы G, то |H| делит |G|. Индекс [G:H] = |G|/|H|-число смежных классов. Следствие: порядок любого элемента делит |G|. Циклическая группа ℤₙ = ⟨1⟩ порождена одним элементом-в ней ровно φ(n) порождающих элементов.

Теорема Лагранжа работает только в конечных группах. Для бесконечных групп (ℤ, GL(n,ℝ)) понятие "индекс" может быть бесконечным.

Гомоморфизмы групп

Гомоморфизм групп f: G → H-отображение, сохраняющее структуру: f(a·b) = f(a)·f(b). Ядро ker(f) = {g ∈ G : f(g) = eₕ}-всегда нормальная подгруппа G. Образ im(f)-подгруппа H. Теорема об изоморфизме: G/ker(f) ≅ im(f).

**Equivariant Neural Networks (E(n)-equivariant):** архитектуры, инвариантные к вращениям и отражениям-SE(3)-Transformer, EGNN. Используются в молекулярном моделировании (AlphaFold использует элементы симметрии 3D-пространства).

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

• **4 аксиомы:** замкнутость, ассоциативность, единица, обратный; все четыре необходимы
• **Теорема Лагранжа:** |H| делит |G|; порядок элемента делит |G|; следствие-малая теорема Ферма (основа RSA)
• **Циклические группы ℤₙ:** порождены одним элементом; φ(n) порождающих элементов; важны в криптографии
• **Гомоморфизм:** f(ab) = f(a)f(b); ker(f)-нормальная подгруппа; теорема об изоморфизме G/ker ≅ im(f)

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

Группы-фундамент абстрактной алгебры и современной физики:

• Кольца и поля — Кольцо = две групповые структуры (сложение + умножение); поле = кольцо с делением
• Теория Галуа — Группа Галуа-группа автоморфизмов поля; определяет разрешимость полиномов
• Кольца и поля — Аддитивная группа кольца + мультипликативная-структура кольца

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

• Почему CNN трансляционно-эквивариантна, но не инвариантна? В чём разница между эквивариантностью и инвариантностью, и когда нужна каждая?
• RSA использует φ(n) = (p−1)(q−1). Что случится с безопасностью RSA, если удастся факторизовать n за полиномиальное время?
• Группа симметрий куба-как она связана с группой перестановок? Сколько элементов в группе вращений куба?

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

• crypto-04-algebraic-structures