Основы теории групп: от модулярной арифметики к криптографии 0:38
Лекция Анкура Моитры из курса MIT OpenCourseWare посвящена введению в теорию групп — мощному математическому аппарату, который позволяет систематизировать алгебраические структуры и объясняет принципы работы современных систем шифрования. Группа — это набор элементов и бинарная операция, удовлетворяющая четырем фундаментальным свойствам: замкнутости, ассоциативности, существованию нейтрального элемента и существованию обратного элемента.
⚖️ Определение группы и примеры 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$), она называется абелевой. Примером бесконечной абелевой группы являются целые числа при сложении. В то же время целые числа при умножении не образуют группу, так как у нуля и многих других элементов нет обратного значения в этом множестве.
📉 Теорема Лагранжа и порядок группы 17:09
Понятие порядка группы — количества её элементов — становится ключевым благодаря теореме Лагранжа. Эта теорема утверждает, что если $H$ является подгруппой конечной группы $G$, то порядок $H$ делит порядок $G$. Это накладывает жесткие ограничения на то, какие подгруппы вообще могут существовать внутри группы.
Для доказательства теоремы используются косеты (смежные классы) — «трансляции» подгруппы $H$, которые разбивают исходную группу $G$ на непересекающиеся части равного размера. Моитра подчеркивает, что доказательство опирается на все аксиомы групп: так, существование обратного элемента гарантирует отсутствие дубликатов при построении косетов.
🔐 Приложения: малая теорема Ферма и Эйлера 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.
🧩 Перспективы: поля и секретные данные
В завершение лекции Моитра вводит понятие поля — структуры с двумя операциями (сложением и умножением), обладающей еще большей упорядоченностью, чем группа. Теорема о том, что многочлен степени $d$ может иметь максимум $d$ корней в поле, является фундаментальной для схем разделения секрета (secret sharing). В таких схемах секрет распределяется среди группы лиц так, что восстановить его могут только те, у кого в совокупности имеется достаточное количество «точек» для восстановления многочлена.
