В group theory у нас уже была важная конструкция:
normal subgroup Normal subgroups нужны не просто как “особые subgroups”. Они позволяют строить:
factor groups / quotient groups То есть мы можем взять группу G, normal subgroup N, склеить элементы по cosets и получить новую группу:
G / N В ring theory происходит похожая история.
Subrings похожи на subgroups, но для построения quotient structures их недостаточно. Нужна более сильная структура:
ideal / идеал Главная идея:
ideal — это subring, …
В прошлой части мы увидели, что ring / кольцо — это структура с двумя операциями:
addition multiplication По addition ring всегда является Abelian group. Но по multiplication всё, как говорится, “хужее”:
не каждый элемент имеет inverse; cancellation может не работать; два ненулевых элемента могут дать 0. Вот последняя штука особенно важна. В обычных integers такого не бывает:
ab = 0 значит:
a = 0 или:
b = 0 Но в некоторых rings это ломается.
Например, в Z6:
2 · 3 = 6 ≡ 0 (mod 6) При этом:
2 != 0 …
До сих пор мы в основном изучали groups / группы. У группы есть одна основная операция. Например:
(Z, +) — integers под сложением.
Или:
U(n) — обратимые элементы modulo n под умножением.
Но у многих привычных множеств существуют сразу две операции:
addition multiplication Например:
integers real numbers integers modulo n matrices polynomials Мы можем складывать integers и можем их умножать. То же самое можно делать с matrices и polynomials. Структура, которая учитывает обе операции одновременно, …
Мы уже знаем, как собирать новые группы с помощью external direct product:
G1 ⊕ G2 ⊕ ... ⊕ Gk Например:
Z4 ⊕ Z2 или:
Z3 ⊕ Z5 Теперь возникает естественный вопрос:
можно ли любую finite Abelian group разобрать на простые cyclic components?
Оказывается, да. Более того, такое разложение по существу единственно.
Именно это утверждает Fundamental Theorem of Finite Abelian Groups / фундаментальная теорема о конечных абелевых группах.
Что именно классифицирует теорема Теорема относится к группам, …
В главе про isomorphisms мы рассматривали отображения, которые показывают, что две группы имеют одну и ту же структуру.
Isomorphism должен:
сохранять group operation; быть one-to-one; быть onto. Но часто нам нужно отображение, которое сохраняет операцию, даже если часть информации при этом теряется. Такое отображение называется group homomorphism / гомоморфизмом групп.
Главная идея Homomorphism переводит элементы одной группы в другую так, чтобы выполнение операции до и после mapping давало …
В главе про cosets мы увидели, что подгруппа N разбивает группу G на left cosets:
aN = {an | n ∈ N} и right cosets:
Na = {na | n ∈ N} В Abelian group left и right cosets совпадают по простой причине: для любых a ∈ G и n ∈ N:
an = na Поэтому:
aN = Na В non-Abelian group отдельные элементы обычно не коммутируют:
an != na Но иногда множества aN и Na всё равно совпадают. При этом необязательно, чтобы:
an = na для одного и того же n. Достаточно, чтобы для каждого n ∈ N нашёлся некоторый n' ∈ 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), но само утверждение не обязано сводиться только к “я знаю секрет”. При …
