# Как теория групп объясняет малую теорему Ферма и RSA

Источник: https://www.youtube.com/watch?v=hUtdHAeyY6Y
Канал: MIT OpenCourseWare
Опубликовано: 17.12.2025

---

## Основы теории групп: от модулярной арифметики к криптографии
[[JUMP:0:38]]

Лекция Анкура Моитры из курса MIT OpenCourseWare посвящена введению в теорию групп — мощному математическому аппарату, который позволяет систематизировать алгебраические структуры и объясняет принципы работы современных систем шифрования. Группа — это набор элементов и бинарная операция, удовлетворяющая четырем фундаментальным свойствам: замкнутости, ассоциативности, существованию нейтрального элемента и существованию обратного элемента.

### ⚖️ Определение группы и примеры
[[JUMP:2:13]]

Понимание теории групп начинается с формализации структур, знакомых из модулярной арифметики. Группа $G$ с операцией $\star$ должна обладать следующими свойствами:

*   **Замкнутость:** для любых $a, b \in G$ результат $a \star b$ также принадлежит $G$.
*   **Ассоциативность:** $(a \star b) \star c = a \star (b \star c)$ для любых $a, b, c \in G$.
*   **Нейтральный элемент ($e$):** такой, что $a \star e = e \star a = a$ для всех $a \in G$.
*   **Обратный элемент:** для каждого $a$ существует $a^{-1}$, такой что $a \star a^{-1} = e$.

Если группа дополнительно обладает свойством коммутативности ($a \star b = b \star a$), она называется абелевой. Примером бесконечной абелевой группы являются целые числа при сложении. В то же время целые числа при умножении не образуют группу, так как у нуля и многих других элементов нет обратного значения в этом множестве.

### 📉 Теорема Лагранжа и порядок группы
[[JUMP:17:09]]

Понятие порядка группы — количества её элементов — становится ключевым благодаря теореме Лагранжа. Эта теорема утверждает, что если $H$ является подгруппой конечной группы $G$, то порядок $H$ делит порядок $G$. Это накладывает жесткие ограничения на то, какие подгруппы вообще могут существовать внутри группы.

Для доказательства теоремы используются косеты (смежные классы) — «трансляции» подгруппы $H$, которые разбивают исходную группу $G$ на непересекающиеся части равного размера. Моитра подчеркивает, что доказательство опирается на все аксиомы групп: так, существование обратного элемента гарантирует отсутствие дубликатов при построении косетов.

### 🔐 Приложения: малая теорема Ферма и Эйлера
[[JUMP:47:11]]

Теория групп позволяет по-новому взглянуть на классические результаты теории чисел. 

Малая теорема Ферма утверждает, что если $p$ — простое число, а $a$ не делится на $p$, то $a^{p-1} \equiv 1 \pmod p$. Доказательство через теорию групп элегантно: степени числа $a$ образуют подгруппу, порядок которой делит порядок группы $(p-1)$. Этот подход также позволяет находить обратный элемент: $a^{p-2} \equiv a^{-1} \pmod p$.

Аналогичный результат, теорема Эйлера, работает для составных модулей: если $m = p \cdot q$, то для чисел, взаимно простых с $m$, выполняется $a^{(p-1)(q-1)} \equiv 1 \pmod m$. По словам Моитры, именно различие в этих степенях при работе с простыми числами и их произведениями делает теорию групп основой для понимания алгоритма RSA.

### 🧩 Перспективы: поля и секретные данные
[[JUMP:109:33]]

В завершение лекции Моитра вводит понятие поля — структуры с двумя операциями (сложением и умножением), обладающей еще большей упорядоченностью, чем группа. Теорема о том, что многочлен степени $d$ может иметь максимум $d$ корней в поле, является фундаментальной для схем разделения секрета (secret sharing). В таких схемах секрет распределяется среди группы лиц так, что восстановить его могут только те, у кого в совокупности имеется достаточное количество «точек» для восстановления многочлена.