В главе про cosets мы увидели, что подгруппа N разбивает группу G на left cosets:
aN = {an | n ∈ N} и right cosets:
Na = {na | n ∈ N} В Abelian group никакой разницы между ними нет, потому что:
an = na Но в non-Abelian group порядок операции важен, поэтому generally:
aN != Na Иногда, однако, left и right cosets всё-таки совпадают для каждого элемента группы. Именно такие подгруппы называются normal subgroups / нормальными подгруппами.
Определение normal subgroup Пусть:
N ≤ G То есть N — …
До сих пор мы в основном изучали отдельные группы. Теперь научимся брать несколько групп и собирать из них одну новую, более крупную группу.
Такая конструкция называется external direct product (внешнее прямое произведение). Главная идея очень простая:
элемент новой группы состоит сразу из нескольких компонентов, а операция выполняется отдельно в каждом компоненте.
Определение Пусть есть группы:
G1, G2, ..., Gn Их external direct product обозначается:
G1 ⊕ G2 ⊕ ... ⊕ Gn Элементы этой группы — …
В этой главе мы плавно перейдём к одной из главных теорем конечной теории групп: Lagrange’s Theorem. Но перед этим нужно понять новый инструмент: coset / смежный класс. Грубо говоря, cosets позволяют разбить группу на одинаковые блоки, построенные из одной подгруппы.
Это потом приводит к важнейшему факту:
порядок подгруппы делит порядок группы.
Но сначала надо понять сами cosets.
Определение: Coset of H in G Пусть G — группа, и:
H ⊆ G — непустое подмножество.
Если взять элемент:
a ∈ G то можно …
Изоморфизм (isomorphism) — это способ формально сказать:
две группы выглядят по-разному, но устроены одинаково.
То есть элементы могут называться по-разному, операция может записываться по-разному, но algebraic structure / алгебраическая структура одна и та же.
Простая аналогия: один человек считает: “one, two, three”, а другой: “eins, zwei, drei”. Слова разные, но оба делают одно и то же — считают.
С группами бывает аналогичная история: одна и та же структура может быть описана разными …
Циклическая группа (cyclic group) — это группа, которую можно полностью получить (сгенерировать) из одного элемента.
Иными словами, если имеется элемент a и если брать его степени:
..., a^-2, a^-1, e, a, a^2, a^3, ... то можно получить всю группу.
Формально:
G = <a> = {a^n | n ∈ Z} Такой элемент a называется generator (генератор). По-простому, один элемент “накручивает” всю группу.
Важная ремарка про notation Если группа записывается в multiplicative notation, то пишут:
a^n Это значит:
a · a · a …
Когда мы уже знаем, что такое группа (group), следующий шаг — понять её внутреннюю структуру.
Для этого вводятся понятия:
порядок группы (order of a group); порядок элемента (order of an element); подгруппа (subgroup); тесты на подгруппу (subgroup tests); порождённая подгруппа (generated subgroup); центр группы (center of a group); централизатор (centralizer). Это всё нужно, чтобы понимать, как группа устроена изнутри.
Порядок группы Порядок группы (order of a group) — это количество элементов в …
Абстрактная алгебра (abstract algebra) изучает не конкретные числа или фигуры, а структуры вида:
множество + операция + свойства операции Главный вопрос: какие свойства имеет операция?
Если разные системы имеют одинаковые свойства, их можно изучать одинаковыми методами.
Например:
целые числа под сложением; симметрии квадрата; матрицы; перестановки; точки на elliptic curve. Все они могут быть группами.
Бинарная операция Пусть:
G — множество.
Бинарная операция (binary operation) на G — это …
В абстрактной алгебре одна из первых реально важных идей такова: иногда разные с виду объекты удобно считать “одинаковыми” — не вообще, а в рамках выбранного правила. Для этого вводится отношение эквивалентности (equivalence relation).
Это не просто формальная академическая муть. Эта идея потом постоянно всплывает в криптографии и zero-knowledge в записях типа:
Z/nZ F_p G/H На первый взгляд блок про эквивалентность кажется простым и почти философским, но это важный кирпич. Без него потом сложнее …
Мы уже говорили о ZK и rollups в одном из уроков по Solidity, который можно посмотреть вот тут:
Но как вообще объяснить идею ZK для тех, кто только входит в эту область? Есть два хороших примера, которые мы сегодня рассмотрим. В первую очередь важно понять основную суть ZK.
Мы (prover) доказываем некому проверяющему наблюдателю (verifier), истинность некоторого утверждения. Часто за этим стоит секретная информация (witness), но само утверждение не обязано сводиться только к “я знаю секрет”. При …
